零 动态规划的定义
斐波那契数列:
1 1 2 3 5 8 13 21 34 55 ….
项:
递推式:
起始项:
目标:
动态规划:更加复杂的递推式
状态:递推项
状态转移方程:递推式
边界:起始项
目标:目标
一 线性DP
1 背包问题
I.01背包
:件数 :背包容量 :第i件物品体积 :第i件物品价值
状态: :将前件物品放入一个容量为的背包能获得的最大价值
状态转移方程:
边界:
目标:
#include <iostream> using namespace std; int n, v, c[110], w[110], f[110][1010]; int main() { cin >> v >> n; for (int i=1; i<=n; i++) cin >> c[i] >> w[i]; for (int i=1; i<=n; i++) for (int j=0; j<=v; j++) if (c[i] <= j) f[i][j] = max(f[i-1][j], f[i-1][j-c[i]]+w[i]); else f[i][j] = f[i-1][j]; cout << f[n][v] << endl; return 0; }
01背包的降维
状态::一个容量为j的背包能装得的最大价值
状态转移方程:
边界:
目标:
#include <iostream> using namespace std; int n, v, c[110], w[110], f[1010]; int main() { cin >> v >> n; for (int i=1; i<=n; i++) cin >> c[i] >> w[i]; for (int i=1; i<=n; i++) for (int j=v; j>=c[i]; j--) f[j] = max(f[j], f[j-c[i]]+w[i]); cout << f[v] << endl; return 0; }
例题
题目描述 Description 妈妈买了N个糖果,想要分给她的双胞胎的孩子(糖果要分成两份)。每个糖果有一个受欢迎程度,用一个整数表示。为了避免不必要的争吵,弟弟和哥哥分得的糖果的受欢迎程度之差必须是一个最小值,且糖果必须全部分完。你能帮帮这位妈妈吗? 输入描述 Input Description 第一行一个整数n,表示糖果数据。 第二行n个数Wi,表示糖果的受欢迎程度,用空格隔开。 输出描述 Output Description 输出分成两堆糖果后的受欢迎程度差的绝对值。 样例输入 Sample Input 5 5 8 13 27 14 样例输出 Sample Output 3 数据范围及提示 Data Size & Hint N (1 ≤ N ≤ 2000) Wi (1 ≤ Wi ≤ 100)
将总重量的一半看为背包容量,往里面放东西,其中能放到最多的容量是为其中某一个人的糖果受欢迎程度,再拿另一个减掉即可。
#include <iostream> using namespace std; int n, v, f[100010], w[10010]; int main() { cin >> n; for (int i=1; i<=n; i++) { cin >> w[i]; v += w[i]; } for (int i=1; i<=n; i++) for (int j=v/2; j>=w[i]; j--) f[j] = max(f[j], f[j-w[i]]+w[i]); cout << v-2*f[v/2] << endl; return 0; }
2 最长不下降子序列()
状态::以结尾的最长不下降子序列的长度
或:前个数,必取 ,能得到的最长不下降子序列的长度
状态转移方程:
边界:
目标:
#include <iostream> using namespace std; int n, a[10010], f[10010], ans; int main() { for (int i=1; i<=n; i++) cin >> a[i]; for (int i=1; i<=n; i++) { f[i] = 1; for (int j=1; j<i; j++) if (a[i] > a[j] && f[j]+1 > f[i]) f[i] = f[j]+1; ans = max(ans, f[i]); } cout << ans << endl; return 0; }
求出最长不下降子序列
其实思想并不难,用来表示最长不下降子序列的前驱,递归输出即可。
#include <iostream> using namespace std; int n, a[10010], f[10010], b[10010], start, ans; //打印以x下标结尾的最长不下降子序列 //第一种 void print_1(int x) { if (x == 0) return ; print_1(b[x]); cout << a[x] << " "; } //第二种 void print_2(int x) { if (b[x] == 0) { cout << a[x] << " "; return ; } print_2(b[x]); cout << a[x] << " "; } int main() { cin >> n; for (int i=1; i<=n; i++) cin >> a[i]; for (int i=1; i<=n; i++) { f[i] = 1; for (int j=1; j<i; j++) if (a[i] >= a[j] && f[j]+1 > f[i]) { f[i] = f[j]+1; b[i] = j; } if (f[i] > ans) { ans = f[i]; start = i; } } print_1(start); cout << endl; print_2(start); cout << endl; return 0; }
求出降序序列的种类数
思路有些复杂:逆序求解,表示以结尾的最长下降序列的种类数,其中有可能会出现重复情况,所以用记录上一次更新的下标,如果重复则不更新。
#include <iostream> using namespace std; int n, a[5005], f[5005], b[5005], last, ans, ans2; int main() { cin >> n; for (int i=1; i<=n; i++) cin >> a[i]; for (int i=n; i>=1; i--) { last = 0; f[i] = 1; b[i] = 1; for (int j=i+1; j<=n; j++) { if (a[i] > a[j]) { if (f[j]+1 > f[i]) { f[i] = f[j]+1; b[i] = b[j]; last = j; } else if (f[j]+1 == f[i] && a[j] != a[last]) { b[i] += b[j]; last = j; } } } if (f[i] > ans) ans = f[i]; } last = 0; for (int i=1; i<=n; i++) { if (f[i] == ans && a[i] != a[last]) { ans2 += b[i]; last = i; } } cout << ans << " " << ans2 << endl; return 0; }
例题
例题一
题目描述 Description Smart很喜欢读书,为了安排自己的读书计划,他会预先把要读的内容做好标记, A B表示一个页段,即第A到B面,当然A<B,若有两个页段A-B,B-C,则可以直接记为A-C,这样,他就可以一次看完,现在告诉你n个页段,请你帮他求出最长的一条页段,并输出这条页段的长度和组成它的页段个数。举个例子: 有 6 个页段: 2-7 1-3 3-12 12-20 7-10 4-50 那么连续的页段就有: 1-3,3-12,12-20长度为20-1+1=20由3个页段组成; 2-7,7-10长度为10-2+1=9由2个页段组成; 4-50长度为50-4+1=47由1个页段组成; 那么最长的一条就是第三个,所以结果为47 1。 需要注意的是:如果有两条不一样的连续的页段长度同时为最大,那么取组成页段数多的一条。 例子: 1-5,5-10,1-10 输出: 10 2 输入描述 Input Description 第一行为一个整数n; 第2行到第n+1行,每行两个整数A B,记录一个页段的信息。 输出描述 Output Description 输出一个整数,即最长的页段的长度和组成它的页段数。 样例输入 Sample Input 7 1 5 10 12 3 10 2 7 2 10 12 16 7 9 样例输出 Sample Output 15 3 数据范围及提示 Data Size & Hint 30%的数据:n<20,0≤A<B≤500; 100%的数据:n≤500,0≤A<B≤500。
首先为了保持有序,建立结构体:
struct book { int st, ed, len; };
其中表示页段起点,表示页段终点,表示页段长度。
按起点大小先排序,之后再仿照问题,列方程:
令为以第个页段为结尾能阅读的最长页码,得:
()
又因为题目要求我们输出页段个数 ,所以再建一个,表示以第个页段为结尾能阅读的最长页码所需的页段个数,则有:
于是就解决了。
#include <iostream> #include <algorithm> using namespace std; struct book { int st, ed, len; }; book a[10010]; bool cmp(book x, book y) { return x.st < y.st; } int f[10010], b[10010], n, ans, res; int main() { cin >> n; for (int i=1; i<=n; i++) { cin >> a[i].st >> a[i].ed; a[i].len = a[i].ed - a[i].st; } sort(a+1, a+1+n, cmp); for (int i=1; i<=n; i++) { f[i] = a[i].len; b[i] = 1; for (int j=1; j<i; j++) { if (a[i].st == a[j].ed && f[j]+a[i].len > f[i]) { f[i] = f[j]+a[i].len; b[i] = b[j]+1; } else if (a[i].st == a[j].ed && f[j]+a[i].len == f[i]) b[i] = max(b[i], b[j]+1); } ans = max(ans, f[i]); } for (int i=1; i<=n; i++) if (f[i] == ans) res = max(res, b[i]); cout << ans+1 << " " << res << endl; return 0; }
例题二
没什么难点,跟上一题差不多,反而简单一点,唯一不同的就是改为:即可
#include <iostream> #include <algorithm> using namespace std; struct speak{ int st, ed, len; };//结构体更方便推算和排序 speak a[10010]; bool cmp(speak x, speak y) { return x.st < y.st; }//自定义cmp函数,用来排序。如果想要更快可重载运算符 int n, f[10010], ans; int main() { cin >> n; for (int i=1; i<=n; i++) { cin >> a[i].st >> a[i].ed; a[i].len = a[i].ed-a[i].st;//时间计算式 } sort(a+1, a+1+n, cmp); for (int i=1; i<=n; i++) { f[i] = a[i].len;//初始化:假设在它前面没有演讲,最短时间也是这个演讲的时间 for (int j=1; j<i; j++) { if (a[j].ed <= a[i].st && f[i] < f[j]+a[i].len) f[i] = f[j]+a[i].len; } ans = max(ans, f[i]);//更新答案 } cout << ans << endl; return 0; }
例题三
n个矩阵排一行。当矩阵a长宽或者宽长小于矩阵b的长宽或者宽长时我们称作矩阵a可以嵌套在矩阵b中。例如(1,2)可以嵌套在(2,3)内,但不能嵌套在(3,1)中。选出一行矩阵,使得每一个矩形都可以嵌套在下一个矩形内(最后一个除外)。 输出一个数,表示最多符合条件的矩形数目
将变成了二维。
其实只要按照长、宽两个关键字来作为“不下降”的指标即可。
但是要注意,有可能矩阵可以翻转,也就是长和宽可以互换。
令为前个矩阵,以第个矩阵作为最外面的一个矩阵,最多能嵌套的矩阵数量。
并且 或 并且
当然,还要排序。因为长和宽可以互换,所以没有唯一的关键字,就应该按面积排序。
#include <iostream> #include <algorithm> using namespace std; struct juxing { int x, y; }; juxing a[10010]; bool cmp(juxing m, juxing n) { return m.x*m.y < n.x*n.y; } int n, f[10010], ans; int main() { cin >> n; for (int i=1; i<=n; i++) cin >> a[i].x >> a[i].y; sort(a+1, a+1+n, cmp); for (int i=1; i<=n; i++) { f[i] = 1; for (int j=1; j<i; j++) { if ( ((a[i].x>a[j].x&&a[i].y>a[j].y) || (a[i].x>a[j].y&&a[i].y>a[j].x)) && f[j]+1>f[i]) { f[i] = f[j]+1; } } ans = max(ans, f[i]); } cout << ans << endl; return 0; }
例题四
题目描述 Description 现在给出n个各不相同的正整数,现在要求从这n个正整数抽出若干个正整数出来,将它们排成从小到大的序列。使得这个序列中任意两个相邻的数之和都是素数。请问这个序列最多能有多少个数字? 输入描述 Input Description 第一行,一个正整数,n 第二行,n个各不相同的正整数,a1 a2 ... an 输出描述 Output Description 第一行,满足条件的序列中数字最多的个数 样例输入 Sample Input 10 9 17 8 5 14 12 13 25 27 30 样例输出 Sample Output 6 数据范围及提示 Data Size & Hint n<=1000,每个整数ai<=1000 题目保证最长序列中不止有一个数字
考虑运用的思想。
因为要从小到大,所以先将原数组排序,再定义表示前个数,必取,相邻的数字和为素数的子序列最长长度。
状态转移方程:
边界:
目标:
#include <iostream> #include <cmath> #include <algorithm> using namespace std; int n, a[10010], f[10010], ans; bool is_prime(int x) { if (x == 0 || x == 1) return false; for (int i=2; i<=sqrt(x); i++) if (x % i == 0) return false; return true; } int main() { cin >> n; for (int i=1; i<=n; i++) cin >> a[i]; sort(a+1, a+1+n); for (int i=1; i<=n; i++) { f[i] = 1; for (int j=1; j<i; j++) { if (is_prime(a[i]+a[j])) f[i] = max(f[i], f[j]+1); } ans = max(ans, f[i]); } cout << ans << endl; return 0; }
3 最长公共子序列()
:序列的前个元素和序列的前个元素能得到的长度
状态转移方程:
边界:
目标:
#include <iostream> #include <string> using namespace std; string A, B; int m, n, f[110][110]; int main() { cin >> A >> B; m = A.size(), n = B.size(); A = ' '+A, B = ' '+B; for (int i=1; i<=m; i++) for (int j=1; j<=n; j++) if (A[i] == B[j]) f[i][j] = f[i-1][j-1]+1; else f[i][j] = max(f[i-1][j], f[i][j-1]); cout << f[m][n] << endl; return 0; }
4 最长公共子上升子序列()
:序列的前个元素和序列的前个元素必取的的长度
状态转移方程:
边界:
目标:
时间复杂度:
#include <iostream> using namespace std; int a[3010], b[3010], n, m, f[3010][3010], ans; int main() { cin >> n; for (int i=1; i<=m; i++) cin >> a[i]; for (int j=1; j<=n; j++) cin >> b[j]; for (int i=1; i<=m; i++) { for (int j=1; j<=n; j++) { if (a[i] == b[j]) { int res = 0; for (int k=1; k<j; k++) if (b[k] < b[j]) res = max(res, f[i-1][k]); f[i][j] = res+1; } else f[i][j] = f[i-1][j]; } } for (int j=1; j<=n; j++) ans = max(ans, f[m][j]); cout << ans << endl; return 0; }
5 数塔问题
:第行第列这个数到数塔顶端能得到的路径上数字之和的最大值
状态转移方程:
边界:
目标:
反着推也可以。
//正着推 #include <iostream> using namespace std; int n, f[1010][1010], a[1010][1010]; int main() { cin >> n; for (int i=1; i<=n; i++) for (int j=1; j<=i; j++) cin >> a[i][j]; for (int j=1; j<=n; j++) f[n][j] = a[n][j]; for (int i=n-1; i>=1; i--) for (int j=1; j<=i; j++) f[i][j] = max(f[i+1][j], f[i+1][j+1]) + a[i][j]; cout << f[1][1] << endl; return 0; }
//反着推 #include <iostream> using namespace std; int f[1010][1010], n, a[1010][1010], ans; int main(){ cin >> n; for(int i=1; i<=n; i++) for(int j=1; j<=i; j++) cin >> a[i][j]; f[1][1] = a[1][1]; for(int i=2; i<=n; i++) for(int j=1; j<=i; j++) f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j]; for(int j=1; j<=n; j++) ans = max(f[n][j], ans); cout << ans << endl; return 0; }
降维
也不难。
表示第列能得到的路径数字最大和。
状态转移方程:
边界:
目标:
#include <iostream> using namespace std; int n, f[1010], a[1010][1010]; int main() { cin >> n; for (int i=1; i<=n; i++) for (int j=1; j<=i; j++) cin >> a[i][j]; for (int j=1; j<=n; j++) f[j] = a[n][j]; for (int i=n-1; i>=1; i--) for (int j=1; j<=i; j++) f[j] = max(f[j], f[j+1]) + a[i][j]; cout << f[1] << endl; return 0; }
求出路径
令记录第行第列的路径前驱为第行的那一列,输出即可。
#include <iostream> using namespace std; int n, b[1010][1010], f[1010][1010], a[1010][1010]; int main() { cin >> n; for (int i=1; i<=n; i++) for (int j=1; j<=i; j++) cin >> a[i][j]; for (int j=1; j<=n; j++) f[n][j] = a[n][j]; for (int i=n-1; i>=1; i--) for (int j=1; j<=i; j++) { if (f[i+1][j] > f[i+1][j+1]) { f[i][j] = f[i+1][j]+a[i][j]; b[i][j] = j; } else { f[i][j] = f[i+1][j+1]+a[i][j]; b[i][j] = j+1; } } int k = 1; for (int i=1; i<=n; i++) { cout << a[i][k] << " "; k = b[i][k]; } cout << endl; return 0; }
6 最大连续子数组和
朴素方法:前缀和。
时间复杂度:
#include<iostream> using namespace std; int n, a[10010], s[10010]; int main() { cin >> n; for (int i=1; i<=n; i++) { cin >> a[i]; s[i] = s[i-1]+a[i]; } for (int i=2; i<=n; i++) for (int j=1; j<i; j++) ans = max(ans, s[i]-s[j]); cout << ans << endl; return 0; }
优化
考虑
前个数字必取 的情况下能得到的最大连续子数组的和。
边界:
目标:
时间复杂度:
#include <iostream> using namespace std; int n, a[100010], f[100010], ans = -1e9; int main() { cin >> n; for (int i=1; i<=n; i++) cin >> a[i]; f[0] = 0; for (int i=1; i<=n; i++) { f[i] = max(f[i-1]+a[i], a[i]); ans = max(ans, f[i]); } cout << ans << endl; return 0; }
求数字个数
令为以 为结尾最大连续子数组和的数字个数,则有:
#include <iostream> using namespace std; int n, a[100010], f[100010], ans = -1e9, b[100010], len; int main() { cin >> n; for (int i=1; i<=n; i++) cin >> a[i]; f[0] = 0; for (int i=1; i<=n; i++) { if (f[i-1]+a[i] >= a[i]) { f[i] = f[i-1]+a[i]; b[i] = b[i-1]+1; } else { f[i] = a[i]; b[i] = 1; } if (ans < f[i]) { ans = f[i]; len = b[i]; } } cout << ans << " " << len << endl; return 0; }
环形数组最大连续子数组和
朴素方法:还是前缀和
时间复杂度:还是
#include <iostream> using namespace std; int n, s[10010], a[10010], ans = -1e9; int main() { cin >> n; for (int i=1; i<=n; i++) { cin >> a[i]; a[i+n] = a[i]; } for (int i=1; i<=2*n; i++) s[i] = s[i-1]+a[i]; for (int i=0; i<=n-1; i++) for (int j=i+1; j<=i+n; j++) ans = max(ans, s[j]-s[i]); cout << ans << endl; return 0; }
优化
仍是
我们发现,环形数组子数组最大和有可能不在环上,也有可能在环上。
所以只要求环上最大和 和 非环上最大和的最大值即可。
非环上最大和很好求,而环上最大和只需要总和减掉最小连续子数组和即可。
而想求最小连续子数组和,只需要将数字取反,求过之后再取反,即可。
#include <iostream> using namespace std; const int INF = 1e9; int n, sum, a[10010], b[10010], f[10010], g[10010], ans1 = -INF, ans1 = -INF; int main() { cin >> n; for (int i=1; i<=n; i++) { cin >> a[i]; b[i] = -a[i]; sum += a[i]; } for (int i=1; i<=n; i++) { f[i] = max(f[i-1]+a[i], a[i]); g[i] = max(g[i-1]+b[i], b[i]); ans1 = max(ans1, f[i]); ans2 = max(ans2, g[i]); } cout << max(ans1, sum+ans2); return 0; }
当你提交时,你会发现:
了。
因为当所有数字为负时,,所以会输出,而实际情况应为负数。
所以我们需要特判,当所有数字为负数时,输出。
时间复杂度:
#include <iostream> using namespace std; const int INF = 1e9; int n, sum, a[10010], b[10010], f[10010], g[10010], ans1 = -INF, ans1 = -INF; bool flag; int main() { cin >> n; for (int i=1; i<=n; i++) { cin >> a[i]; b[i] = -a[i]; if (a[i] > 0) flag = true; sum += a[i]; } for (int i=1; i<=n; i++) { f[i] = max(f[i-1]+a[i], a[i]); g[i] = max(g[i-1]+b[i], b[i]); ans1 = max(ans1, f[i]); ans2 = max(ans2, g[i]); } if (flag) cout << max(ans1, sum+ans2); else cout << ans1 << endl; return 0; }
7 最大子矩阵和问题
朴素方法: 、、不等,全是暴力,不讲。
考虑
设表示第列从第行到第行的前缀和,为第列第行到第行的和,则有:
令表示第列前最大的子矩阵和,则有:
边界:
目标:
#include <iostream> using namespace std; int n, a[1010][1010], sum[1010][1010], b[1010], f[1010], ans = -1e9; int main() { cin >> n; for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { cin >> a[i][j]; sum[j][i] = sum[j][i-1]+a[i][j]; } for (int i=1; i<=n; i++) for (int j=i; j<=n; j++) for (int k=1; k<=n; k++) { b[k] = sum[k][j]-sum[k][i-1]; f[k] = max(b[k], f[k-1]+b[k]); ans = max(ans, f[k]); } cout << ans << endl; return 0; }
例题
例题一
简化题意:求不包括的最大子矩阵和。
如果想排除掉的话,硬搞是很难的。
我们可以考虑将改成,再套一下模板即可。
但注意,这样搞的风险就是有可能结果是负数,而现实中不可能。
所以特判一下,当为负数时,输出即可。
时间复杂度:
#include <iostream> using namespace std; const int INF = 1e9; long long n, m, a[1010][1010], f[1010], b[1010], ans = -INF, sum[1010][1010]; int main() { cin >> n >> m; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { cin >> a[i][j]; if (a[i][j] == 0) a[i][j] = -INF; sum[j][i] = sum[j][i-1]+a[i][j]; } for (int i=1; i<=n; i++) for (int j=i; j<=n; j++) for (int k=1; k<=m; k++) { b[k] = sum[k][j]-sum[k][i-1]; f[k] = max(b[k], f[k-1]+b[k]); ans = max(ans, f[k]); } if (ans < 0) ans = 0; cout << ans << endl; return 0; }
8 编辑距离
不知道编辑距离的,可以看这道题目:
【问题描述】 设A和B是两个字符串。我们要用最少的字符操作次数,将字符串A转换为字符串B。这里所说的字符操作共有三种: 1、删除一个字符; 2、插入一个字符; 3、将一个字符改为另一个字符。 【编程任务】 对任的两个字符串A和B,计算出将字符串A变换为字符串B所用的最少字符操作次数。
:将的前个字母变为的前个字母所需的最少的操作次数。
状态转移方程:
:更换
:删除
:添加
边界:
目标:
#include <iostream> #include <string> using namespace std; string a, b; int f[1010][1010], n, m; int main() { cin >> a >> b; m = a.size(), n = b.size(); a = ' '+a, b = ' '+b; for (int i=1; i<=m; i++) f[i][0] = i; for (int i=1; i<=n; i++) f[0][i] = i; for (int i=1; i<=m; i++) for (int j=1; j<=n; j++) { f[i][j] = 1e9; if (a[i] == b[j]) f[i][j] = f[i-1][j-1]; else f[i][j] = min(f[i-1][j-1], min(f[i][j-1], f[i-1][j]))+1; } cout << f[m][n] << endl; return 0; }
例题
例题一
状态定义
根据题意,很简单,就是:
表示串的前个字母与串的前个字母的最小距离。
状态转移方程
对于来说,无疑就三种情况:
与的码绝对值之差
对应着空格
对应着空格
显然,第一种的方程最好写:
而第二种,由于对应着空格,所以,状态一定要从串的前个字母与串的前个字母的最小距离推得。
所以,第二个方程为:
同理,第三个方程为:
即为三者最小值。
边界
从和入手。
先从定义出发,表示串的前个字母与串的前个字母的最小距离.
是不是很怪?
所以我们只能默认第零个字母为空格,所以:
化简一下,就是:
同理,
目标
设串长度为, 串长度为,目标易求:
#include <iostream> #include <string> #include <cmath> using namespace std; string a, b; int m, n, f[2010][2010], k; int main() { cin >> a >> b; cin >> k; m = a.size(), n = b.size(); a = ' '+a, b = ' '+b;// 因为string下标从零开始,所以利用string加法的特性,开头加空格 for (int i=1; i<=m; i++) f[i][0] = i*k; for (int j=1; j<=n; j++) f[0][j] = j*k; for (int i=1; i<=m; i++) for (int j=1; j<=n; j++) { f[i][j] = 1e9; // 因为要取最小,所以初值要赋大 f[i][j] = min(f[i-1][j-1]+abs(a[i] - b[j]), min(f[i-1][j]+k, f[i][j-1]+k)); //求三者最小值可用min套min } cout << f[m][n] << endl; return 0; }
9 方格取数
不知道的戳这
:第一次走到了,第二次走到,两次能取到的数字之和的最大值。
状态转移方程:
边界:
目标:
#include <iostream> using namespace std; int f[11][11][11][11], a[11][11], n; int main() { cin >> n; int x, y, z; while (cin >> x >> y >> z, x && y && z) a[x][y] = z; for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int k=1; k<=n; k++) for (int l=1; l<=n; l++) { f[i][j][k][l] = max(max(f[i-1][j][k-1][l], f[i-1][j][k][l-1]), max(f[i][j-1][k-1][l], f[i][j-1][k][l-1]))+a[i][j]; if (i != k || j != l) f[i][j][k][l] += a[k][l]; } cout << f[n][n][n][n] << endl; return 0; }
降维
:两次都走了步,第一次走到第行,第二次走到了第行,两次能取到的数字之和的最大值。
状态转移方程:
边界:
目标:
#include <iostream> using namespace std; int n, a[11][11], f[31][11][11]; int main() { cin >> n; int x, y, z; while (cin >> x >> y >> z, x && y && z) a[x][y] = z; for (int i=1; i<=2*n-1; i++) for (int j=1; j<=n; j++) for (int k=1; k<=n; k++) { f[i][j][k] = max(max(f[i-1][j-1][k-1], f[i-1][j][k-1]), max(f[i-1][j-1][k], f[i-1][j][k])); f[i][j][k] += a[j][i-j+1]; if (j != k) f[i][j][k] += a[k][i-k+1]; } cout << f[2*n-1][n][n] << endl; return 0; }
10 乘积最大
:前个数插入个乘号能得到的最大乘积
状态转移方程:
边界:
目标:
#include <iostream> #include <string> using namespace std; int n, m, f[51][11], num[51][51]; string x; int main() { cin >> n >> m; cin >> x; x = ' '+x; for (int i=1; i<=n; i++) for (int j=i; j<=n; j++) num[i][j] = num[i][j-1]*10+x[j]-'0'; for (int i=1; i<=n; i++) f[i][0] = num[1][i]; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) for (int k=j; k<i; k++) f[i][j] = max(f[i][j], f[k][j-1]*num[k+1][i]); cout << f[n][m] << endl; return 0; }
11杂题
题目描述 Description 小Y最近当上了农场主!不过,还没有来得及庆祝,一件棘手的问题就摆在了小Y的面前。农场的栅栏,由于年久失修,出现了多处破损。栅栏是由n块木板组成的,每块木板可能已经损坏也可能没有损坏。小Y知道,维修连续m个木板(这m个木板不一定都是损坏的)的费用是sqrt(m)。可是,怎样设计方案才能使总费用最低呢?小Y想请你帮帮忙。 输入描述 Input Description 输入文件的第一行包含一个整数n (n<=2500),表示栅栏的长度。 第二行包含n个由空格分开的整数(长整型范围内)。如果第i个数字是0,则表示第i块木板已经损坏,否则表示没有损坏。 输出描述 Output Description 输出文件中仅包含一个实数,表示最小维修费用。注意:答案精确到小数点后3位。 样例输入 Sample Input 9 0 –1 0 1 2 3 0 –2 0 样例输出 Sample Output 3.000
令为修好前块木板的最小花费,则有
边界:
目标:
#include <iostream> #include <cmath> #include <cstdio> using namespace std; int n, a[2510]; double f[2510]; int main() { cin >> n; for (int i=1; i<=n; i++) cin >> a[i]; for (int i=1; i<=n; i++) if (a[i] != 0) f[i] = f[i-1]; else { f[i] = 1e9; for (int j=1; j<=i; j++) f[i] = min(f[i], f[i-j]+sqrt(j)); } printf("%.3f\n", f[n]); return 0; }
题目描述 Description 聪聪的游戏全校同学都很喜欢,老师表扬了聪聪。放学回家以后,发现小表弟在家,妈妈告诉表弟:“聪聪哥哥特别会玩游戏,你让聪聪哥哥陪你玩啊!,小表弟就拿出他的积木”让聪聪陪他玩,聪聪开始不想在家陪表弟,他想和同学出去玩呢,可是妈妈说,如果陪表弟玩开心了,周末就带他去游乐场。听了这话,聪聪就跟妈妈保证,一定好好陪小表弟玩。聪聪一边拿着表弟的积木,一边在想,平常的游戏表弟都玩腻了,有什么新的好玩的呢。不一会聪聪就想到了,小表弟的这组积木有个底盘,是由很多方格组成的,积木中正好有一些与方格大小相同的正方形积木,聪聪和小表弟一起按如下规则将这些正方形积木摆放在底盘上:底盘的每一竖行方格组成一列,必须从最左边的一列开始摆放,每列从最下面的方格开始连续摆放积木,底盘至少要放两列,后一列放的积木数至少比前一列多一个。聪聪一边教表弟一边摆出不同积木数的各种情况。 这个游戏启发了聪聪,他想:如果积木底盘无限大,当积木数很多时,能摆放的情况就有很多很多,你能计算出有 N 个积木时按照上述规则能摆放出多少种情况吗? 输入描述 Input Description 一个正整数 N(N≥3),表示积木个数。 输出描述 Output Description 一个正整数,表示能摆放出的情况数。 样例输入 Sample Input 5 样例输出 Sample Output 2 数据范围及提示 Data Size & Hint 【数据范围】 对于 40%的数据满足 N≤10; 对于 80%的数据满足 N≤100; 对于 100%的数据满足 N≤200。
:共摆放个积木,最后一列不超过个积木,的方案总数。
状态转移方程:
边界:
目标:
#include <iostream> using namespace std; int n, f[205][205]; int main() { cin >> n; f[0][0] = 1; for (int i=0; i<=n; i++) for (int j=1; j<=n; j++) if (i<j) f[i][j] = f[i][j-1]; else f[i][j] = f[i-j][j-1]+f[i][j-1]; cout << f[n][n]-1 << endl; return 0; }
对于第一个子任务,直接贪心,能取多少取多少,取满后清零再取。
对于第二个子任务,考虑。
设表示前个教徒的最少危险值,则有:
其中表示之间的危险值。
问题来了:怎么求呢?
在跑方程的时候暴力求解。
时间复杂度:,显然会。
预处理。
令为计数器,当发现新的宗教时,并且标记这个宗教,而每一段对应的即为
时间复杂度:,可过。
至于边界,显然有
目标自然是
(代码中的即为)
#include <iostream> #include <cstring> using namespace std; int n, m, k, a[10010], cnt, ans, sum[1010][1010], f[1010]; bool vis[10010]; int main() { cin >> n >> m >> k; for (int i=1; i<=n; i++) cin >> a[i]; for (int i=1; i<=n; i++) { cnt = 0; memset(vis, false, sizeof(vis));// 一定要清空! for (int j=i; j<=n; j++) { if (!vis[a[j]]) { vis[a[j]] = true; cnt++; } sum[i][j] = cnt; } } cnt = 0; memset(vis, false, sizeof(vis));//注意,出来时也要清空!我被坑了好长时间TAT for (int i=1; i<=n; i++) { if (!vis[a[i]]) { vis[a[i]] = true; cnt++; } if (cnt > k) { ans++; cnt = 1; memset(vis, false, sizeof(vis));//记得清空! vis[a[i]] = true; } if (i == n) ans++; } cout << ans << endl; f[0] = 0; f[1] = 1;//初始化莫忘掉 for (int i=2; i<=n; i++) { f[i] = 1e9;//因为取最小值,所以初值要赋大 for (int j=1; j<=i; j++) if (sum[j][i] <= k) //而且危险值不能超过k f[i] = min(f[i], f[j-1]+sum[j][i]); } cout << f[n] << endl; return 0; }