任务说明：这也是基础的动态规划。是在线性结构上面的动态规划，一定要掌握。
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)做的。
#include <bits/stdc++.h>
using namespace std; int N; int calLis(int height[], int endd) {
int dp[endd + ];
for (int i = ; i <= endd; ++i) {
dp[i] = ;
for (int j = ; j < i; ++j) {
if (height[i] > height[j]) {
dp[i] = max(dp[i], dp[j]+);
}
}
}
int answer = ;
for (int i = ; i < endd + ; ++i) {
answer = max(answer, dp[i]);
}
return answer;
} int calLds(int height[], int start) {
int dp[N];
memset(dp, , sizeof(dp));
for (int i = start; i < N; ++i) {
dp[i] = ;
for (int j = start; j < i; ++j) {
if (height[i] < height[j]) {
dp[i] = max(dp[i], dp[j] + );
}
}
}
int answer = ;
for (int i = start; i < N; ++i) {
answer = max(answer, dp[i]);
}
return answer;
} int main () {
cin >> N;
int height[N];
for (int i = ; i < N; ++i) {
cin >> height[i];
} int max_len = ;
for (int i = ; i < N; ++i) {
int len = ;
if (i == ) {
len = calLds(height, );
} else if (i == N - ) {
len = calLis(height, N-);
} else {
len = calLis(height, i) + calLds(height, i+);
}
max_len = max(max_len, len);
}
cout << N - max_len << endl;
return ;
}
尼克的任务
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)
//区间DP
#include <bits/stdc++.h> using namespace std; int arr[];
int t[]; // t[i] 表示前i堆石子的总数（前缀和）
int dp_min[][]; // dp[i][j] 表示第i堆到第j堆的最小||最大代价
int dp_max[][]; // dp[i][j] 表示第i堆到第j堆的最小||最大代价 void print(int T[][], int N) {
for (int i = ; i < * N; ++i) {
for (int j = ; j < * N; ++j) {
if (T[i][j] == 0x7F7F7F7F) {
printf("INF ");
} else {
printf("%3-d ", T[i][j]);
}
}
printf("\n");
}
} void print(int T[], int N) {
for (int i = ; i <= * N; ++i) {
printf("%d ", T[i]);
}
printf("\n");
} int main() {
int N;
cin >> N; for (int i = ; i < N; ++i) {
cin >> arr[i];
arr[i+N] = arr[i]; //2*N, 拆环为链
} memset(t, , sizeof(t));
for (int i = ; i <= * N; ++i) {
t[i] = t[i-] + arr[i-];
}
memset(dp_min, 0x7F, sizeof(dp_min));
memset(dp_max, , sizeof(dp_max));
/*
printf("=======debug========T done=========\n");
print(t, N);
printf("=======debug========dp_min init=========\n");
print(dp_min, N);
printf("=======debug========dp_max init=========\n");
print(dp_max, N);
*/
for (int i = *N - ; i >= ; --i) {
for (int j = i; j < *N; ++j) {
if (i == j) {
dp_min[i][i] = dp_max[i][i] = ;
} else {
for (int k = i; k < j; ++k) {
dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k+][j] + t[j+] - t[i]);
dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k+][j] + t[j+] - t[i]);
}
}
}
}
/*
printf("=======debug========dp_min done=========\n");
print(dp_min, N);
printf("=======debug========dp_max done=========\n");
print(dp_max, N);
*/
int ans_maxx = , ans_minn = INT_MAX;
for (int i = ; i < N; ++i) {
if (dp_max[i][N+i-] > ans_maxx) {
ans_maxx = dp_max[i][N+i-];
}
if (dp_min[i][N+i-] < ans_minn) {
ans_minn = dp_min[i][N+i-];
}
}
cout << ans_minn << endl << ans_maxx << endl;
return ;
}
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。
// P1108 低价购买
#include <bits/stdc++.h> using namespace std; int main() {
int N;
cin >> N;
int price[N];
for (int i = ; i < N; ++i) {
cin >> price[i];
} //[1] 用LIS来计算dp数组
int dp[N];
int ans_length = ; //一开始边界写成0了，82分.. 最短的长度就是1
for (int i = ; i < N; ++i) {
dp[i] = ;
for (int j = ; j < i; ++j) {
if (price[i] < price[j]) {
dp[i] = max(dp[i], dp[j] + );
ans_length = max (dp[i], ans_length);
}
}
}
//[2] 求方案数 || 怎么去重是关键.
int methods[N];
for (int i = ; i < N; ++i) {
methods[i] = ;
if (dp[i] == ) {
methods[i] = ;
//continue; 写了continue会wa
//举个例子 price数组是 [2, 1, 2, 3], 计算出来的dp数组是 [1, 2, 1, 1]; 其实method数组应该是 [0, 1, 1, 1];
//但是如果continue的话就是 [1, 1, 1, 1]
}
for (int j = ; j < i; ++j) {
// 难点---如何去重的分支
if (price[i] == price[j] && dp[i] == dp[j]) {
methods[j] = ;
}
else if (price[i] < price[j] && dp[i] == dp[j]+) {
methods[i] += methods[j];
}
}
} int ans_methods = ;
for (int i = ; i < N; ++i) {
if (dp[i] == ans_length) {
ans_methods += methods[i];
}
}
cout << ans_length << " " << ans_methods << endl;
return ;
}
多米诺骨牌