最基本的思想依旧是分治，对于每段区间都由更小的区间最优值组合得到。
Step://模板 //区间最优解
变量：
dp[i][j]：区间[i,j]的最优解（dp[i][i]对角线视情况而定）；
k：每次将区间[i,j]分为更小的区间组合[i,k]+[k,j]；
三层循环：
最外层：for(int l=1;l<=len;l++) //区间长度枚举
第二层：for(int i=1;i<=len-l+1;i++) //起点+终点枚举
int j=i+l-1; dp[i][j]=***;
内层： for(int k=i;k<j;k++) //枚举区间内部分割点k
dp[i][j]=max/min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sun[i-1]);
Step://模板 //区间计数 //另一种写法？？ //还是要灵活一点，这些是最最简单基础的板子
变量：
dp[i][j]：区间[i,j]的最优解（dp[i][i]对角线视情况而定）；
k：每次将区间[i,j]分为更小的区间组合[i,k]+[k,j]；
记得初始化dp；
三层循环：
最外层：for(int i=1;i<=n;i++) //枚举起点
第二层：for(int j=i+1;j<=n;j++ //终点枚举
//有时需要处理dp[i][j]
内层： for(int k=i;k<=j;k++) //枚举区间内部分割点k
dp[][]递推式
简单的基础题（中文题……不解释）：
1.石子归并
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> using namespace std; int n, sum[105],a; int dp[105][105]; int main() { while (cin>>n) { sum[0] = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a); sum[i] = sum[i - 1] + a; } memset(dp, 0, sizeof(dp)); for(int l=2;l<=n;l++) for (int i = 1; i <= n - 1 + 1; i++) { int j = i + l - 1; dp[i][j] = 0x3f3f3f3f; for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i - 1]); } } printf("%d ", dp[1][n]); } return 0; }
POJ 2955 括号匹配
求括号匹配的最大值
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<string> using namespace std; typedef long long ll; int n; int dp[110][110]; string s; int main() { while (cin>>s) { int len = s.length(); memset(dp, 0, sizeof(dp)); for(int l=2;l<=len;l++) for (int i = 0; i <= len - l+1 ; i++) { int j = i + l-1 ; if ((s[i] =='('&& s[j]==')')||(s[i]=='['&&s[j]==']')) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = dp[i + 1][j - 1]; for (int k = i; k < j; k++) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]); } } cout << dp[0][len - 1] << endl; } return 0; }
改了好久啊……这个……
emmmmmmm跟前面的题还是稍微有些不太一样，这里需要逆向推(正向推的话，需要考虑的情况有很多，当前衣服跟前面的衣服有没有一样的啊，是脱了还是还在里面套着啥的……总之就是很乱很杂的感觉？？但是，如果逆向考虑的话，只需要看当前衣服是不是只在此时使用)，下面来看一看递推的式子↓
很容易想到，如果最i处的衣服只在i处使用，那么dp[i][j]=dp[i+1][j]+1；
如果i处衣服在j处也使用的话（a[i]==a[j]）,那么dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);
ps：不要忘记初始化dp
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<string> using namespace std; typedef long long ll; int n,a[110],t; int dp[110][110]; int main() { cin >> t; int cnt = 0; while (t--) { cin >> n; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) { cin >> a[i]; dp[i][i] = 1; } for (int i = n-1; i >0; i--) { for (int j = i + 1; j <= n; j++) { dp[i][j] = dp[i + 1][j] + 1; for (int k = i; k <=j; k++) { if (a[i] == a[k]) dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]); } } } cout << "Case "<<++cnt<<": " << dp[1][n] << endl;; } return 0; }
NYOJ 746 整数划分
emmmm……都写到注释里了，，，（自己还是写不出来，，，还是要看别人的题解orz，不要方！人一我百，人十我万！早晚会写出来的）
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<string> using namespace std; typedef long long ll; int n,t,m; ll a[25][25]; ll dp[25][25];//表示到i为止，填j个乘号的最大值 string s; int main() { cin >> t; while (t--) { cin >> s>>m; m--; //拆分为m组数的乘积，添加m-1个* n = s.length(); for (int i = 0; i < n; i++) //字符串转换为数 { a[i][i] = s[i] - '0'; for (int j = i + 1; j < n; j++) a[i][j] = a[i][j - 1] * 10 + s[j] - '0'; } memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) //初始化dp，dp[i][0]→不添*→a[0][i] dp[i][0] = a[0][i]; for (int j = 1; j <= m; j++) //枚举添*的个数 for (int i = j; i < n; i++) //添加j个*至少有i+1个数，i+1个数有i个间隔，所以初始条件为i=j（此处s下标是从0开始的） for (int k = 0; k < i; k++)//枚举*添加的位置 dp[i][j] = max(dp[i][j], dp[k][j - 1] * a[k+1][i]); //最优解为此时dp[i][j]和添加j-1个*时的dp[k][j-1]与末尾数值的乘积 cout << dp[n-1][m] << endl; } return 0; }
hdu 4238 You are the one
dp[i][j]：i~j的最优解（不考虑i之前和j之后的人，只考虑[i,j]）
递推公式：dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+d[i]*(k-i)+(sum[j]-sum[k])*(k-i+1));
把黑屋子看成栈，对于每个区间[i,j]，考虑将i扔到黑屋子里去~然后枚举出栈的位置~
i处进栈k处出栈，上台顺序就变为i+1,i+2......i,k+1,k+2.....j最优为min(dp[i+1][k]+dp[k+1][j]+d[i]*(k-i)+(sum[j]-sum[k])*(k-i+1));
//只考虑[i,j],看成把i~j单独拿出来的子列 ↑i前面有(k-i)个人 ↑k+1~j前面有(k-i+1)个人
#include<iostream> #include<string> #include<algorithm> using namespace std; int t,dp[105][105],d[105],n; int sum[105]; int main() { cin >> t; for (int m = 1; m <= t; m++) { memset(dp, 0, sizeof(dp)); cin >> n; sum[0] = 0; for (int i = 1; i <= n; i++) { cin >> d[i]; sum[i] = sum[i - 1] + d[i]; } for(int l=1;l<n;l++) for (int i = 1; i <= n - l; i++) { int j = i + l; if(i<j) dp[i][j] = 0x3f3f3f3f; for (int k = i; k <= j; k++) { dp[i][j] = min(dp[i][j], dp[i+1][k] + dp[k + 1][j] + d[i] * (k - i) + (sum[j] - sum[k])*(k - i+1)); } } cout <<"Case #"<<m<<": "<< dp[1][n] << endl; } return 0; }
hdu 2476
#include<iostream> #include<string> #include<algorithm> using namespace std; int dp[105][105]; int ans[105]; string s, t; int main() { while (cin >> s) { cin >> t; int len = t.length(); memset(dp, 0, sizeof(dp)); for(int j=0;j<len;j++) { for(int i=j;i>=0;i--) { dp[i][j] = dp[i + 1][j] + 1; for (int k = i+1; k <= j; k++) if(t[i]==t[k]) dp[i][j] = min(dp[i][j], dp[i+1][k] + dp[k + 1][j]); } } for(int i=0;i<len;i++) ans[i] = dp[0][i]; for (int i = 0; i < len; i++) { if (s[i] == t[i]) ans[i] = ans[i - 1]; else { for (int j = 0; j < i; j++) ans[i] = min(ans[i], ans[j] + dp[j + 1][i]); } } cout << ans[len - 1] << endl; } return 0; }