任务说明：这也是基础的动态规划。是在线性结构上面的动态规划，一定要掌握。
P1020 导弹拦截
导弹拦截
P1091 合唱队形
老师给同学们排合唱队形。N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
解答：前面是LIS, 后面是LDS，枚举每一个中心点的位置，求出来之后长度相加，然后减一下。O(nlogn)的LIS还是不会写。用O(N^2)做的。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int N; 5 6 int calLis(int height[], int endd) { 7 int dp[endd + 1]; 8 for (int i = 0; i <= endd; ++i) { 9 dp[i] = 1; 10 for (int j = 0; j < i; ++j) { 11 if (height[i] > height[j]) { 12 dp[i] = max(dp[i], dp[j]+1); 13 } 14 } 15 } 16 int answer = 0; 17 for (int i = 0; i < endd + 1; ++i) { 18 answer = max(answer, dp[i]); 19 } 20 return answer; 21 } 22 23 int calLds(int height[], int start) { 24 int dp[N]; 25 memset(dp, 0, sizeof(dp)); 26 for (int i = start; i < N; ++i) { 27 dp[i] = 1; 28 for (int j = start; j < i; ++j) { 29 if (height[i] < height[j]) { 30 dp[i] = max(dp[i], dp[j] + 1); 31 } 32 } 33 } 34 int answer = 0; 35 for (int i = start; i < N; ++i) { 36 answer = max(answer, dp[i]); 37 } 38 return answer; 39 } 40 41 int main () { 42 cin >> N; 43 int height[N]; 44 for (int i = 0; i < N; ++i) { 45 cin >> height[i]; 46 } 47 48 int max_len = 0; 49 for (int i = 0; i < N; ++i) { 50 int len = 0; 51 if (i == 0) { 52 len = calLds(height, 0); 53 } else if (i == N - 1) { 54 len = calLis(height, N-1); 55 } else { 56 len = calLis(height, i) + calLds(height, i+1); 57 } 58 max_len = max(max_len, len); 59 } 60 cout << N - max_len << endl; 61 return 0; 62 }
尼克的任务
P1880 石子合并-------(这个就是区间dp)
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分。
这个题目做的我好绝望啊...不会不会不会，消耗了一个下午orz
解答：
首先我们先不管是不是环形的操场，直接看成一条线段。
假设只有一堆或者两堆石子， 那么只有一种方案。
那么假设有三堆石子呢，（（1， 2），3） ；（1，（ 2，3））。
如果有k堆石子呢？-------- 最终都会变成两堆。如果我们把最后两堆分开，左边和右边无论怎么合并，都必须满足最优合并方案，整个问题才能得到最优解
• 每次只能合并相邻的两堆 → 合并成一个点的一定是一个区间
• 每次的得分 → 如果确定了当前区间的起点和重点，得分就是这个区间内石子的总数量
所以转移方程如下：
• T[i][j]：从第 i 堆到第 j 堆的石子数的总和
• F[i][j]：从第 i 堆石子合并到第 j 堆石子的最小的得分
• F[i][j] = min { F[i][k] + F[k+1][j] + t[i][j] } ( i <= k < j )
• 复杂度O(n^3)
最后处理一下环形怎么办：
方法1： 枚举起点 — O(n^4)
方法2：把长度变成2*n — O(8n^3) = O(n^3)
1 //区间DP 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 int arr[220]; 7 int t[220]; // t[i] 表示前i堆石子的总数（前缀和） 8 int dp_min[220][220]; // dp[i][j] 表示第i堆到第j堆的最小||最大代价 9 int dp_max[220][220]; // dp[i][j] 表示第i堆到第j堆的最小||最大代价 10 11 void print(int T[][220], int N) { 12 for (int i = 0; i < 2 * N; ++i) { 13 for (int j = 0; j < 2 * N; ++j) { 14 if (T[i][j] == 0x7F7F7F7F) { 15 printf("INF "); 16 } else { 17 printf("%3-d ", T[i][j]); 18 } 19 } 20 printf(" "); 21 } 22 } 23 24 void print(int T[], int N) { 25 for (int i = 0; i <= 2 * N; ++i) { 26 printf("%d ", T[i]); 27 } 28 printf(" "); 29 } 30 31 int main() { 32 int N; 33 cin >> N; 34 35 for (int i = 0; i < N; ++i) { 36 cin >> arr[i]; 37 arr[i+N] = arr[i]; //2*N, 拆环为链 38 } 39 40 memset(t, 0, sizeof(t)); 41 for (int i = 1; i <= 2 * N; ++i) { 42 t[i] = t[i-1] + arr[i-1]; 43 } 44 memset(dp_min, 0x7F, sizeof(dp_min)); 45 memset(dp_max, 0, sizeof(dp_max)); 46 /* 47 printf("=======debug========T done========= "); 48 print(t, N); 49 printf("=======debug========dp_min init========= "); 50 print(dp_min, N); 51 printf("=======debug========dp_max init========= "); 52 print(dp_max, N); 53 */ 54 for (int i = 2*N - 1; i >= 0; --i) { 55 for (int j = i; j < 2*N; ++j) { 56 if (i == j) { 57 dp_min[i][i] = dp_max[i][i] = 0; 58 } else { 59 for (int k = i; k < j; ++k) { 60 dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k+1][j] + t[j+1] - t[i]); 61 dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k+1][j] + t[j+1] - t[i]); 62 } 63 } 64 } 65 } 66 /* 67 printf("=======debug========dp_min done========= "); 68 print(dp_min, N); 69 printf("=======debug========dp_max done========= "); 70 print(dp_max, N); 71 */ 72 int ans_maxx = 0, ans_minn = INT_MAX; 73 for (int i = 0; i < N; ++i) { 74 if (dp_max[i][N+i-1] > ans_maxx) { 75 ans_maxx = dp_max[i][N+i-1]; 76 } 77 if (dp_min[i][N+i-1] < ans_minn) { 78 ans_minn = dp_min[i][N+i-1]; 79 } 80 } 81 cout << ans_minn << endl << ans_maxx << endl; 82 return 0; 83 }
P1108 低价购买
题意就是给出 N 天的股票价格， 购买的原则是 【低价购买，再低价购买】， 求出最大购买次数和拥有最大购买次数的方案数（要求价格序列一致的时候要去重）。
解答：第一问：最长下降子序列的长度。(模板) 第二问：求去重后的方案数。（难点）
看了题解，学习了下答案：
设置一个methods[i]数组， 表示以price[i]为结尾的序列的最大购买方案数。
如果说 price[i] == price[j] && dp[i] == dp[j] && i > j ， 那么就把 method[j] = 0. //解释一下就是如果有两天价格一样，并且这两天的LDS也一样，就把一天的方案数置为0.
为什么需要置前一天的方案数为0，而不是后一天？ --> 因为能转移到前一天的方案 也一定能转移到后一天， 反之不行。
举个例子： price = [9 , 8 , 10, 8, 1] -> dp = [1, 2, 1, 2, 3] -> price有两个8。第一个8的方案数是 1 (对应的方案是 【9， 8】)， 第二个8的方案数其实是 2 (对应的方案是 【9， 8】【10， 8】)。 因为【9， 8】 就是重复的，所以把第一个8的methods置为0。
1 // P1108 低价购买 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 int main() { 7 int N; 8 cin >> N; 9 int price[N]; 10 for (int i = 0; i < N; ++i) { 11 cin >> price[i]; 12 } 13 14 //[1] 用LIS来计算dp数组 15 int dp[N]; 16 int ans_length = 1; //一开始边界写成0了，82分.. 最短的长度就是1 17 for (int i = 0; i < N; ++i) { 18 dp[i] = 1; 19 for (int j = 0; j < i; ++j) { 20 if (price[i] < price[j]) { 21 dp[i] = max(dp[i], dp[j] + 1); 22 ans_length = max (dp[i], ans_length); 23 } 24 } 25 } 26 //[2] 求方案数 || 怎么去重是关键. 27 int methods[N]; 28 for (int i = 0; i < N; ++i) { 29 methods[i] = 0; 30 if (dp[i] == 1) { 31 methods[i] = 1; 32 //continue; 写了continue会wa 33 //举个例子 price数组是 [2, 1, 2, 3], 计算出来的dp数组是 [1, 2, 1, 1]; 其实method数组应该是 [0, 1, 1, 1]; 34 //但是如果continue的话就是 [1, 1, 1, 1] 35 } 36 for (int j = 0; j < i; ++j) { 37 // 难点---如何去重的分支 38 if (price[i] == price[j] && dp[i] == dp[j]) { 39 methods[j] = 0; 40 } 41 else if (price[i] < price[j] && dp[i] == dp[j]+1) { 42 methods[i] += methods[j]; 43 } 44 } 45 } 46 47 int ans_methods = 0; 48 for (int i = 0; i < N; ++i) { 49 if (dp[i] == ans_length) { 50 ans_methods += methods[i]; 51 } 52 } 53 cout << ans_length << " " << ans_methods << endl; 54 return 0; 55 }
多米诺骨牌