区间DP
经典石子合并问题V1 复杂度 On3
int a[SZ], sum[SZ], f[SZ][SZ]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i]; } for(int len = 2; len <= n; len++) { for(int l = 1; l <= n-len+1; l++) { int r = l+len-1; int ans = INF; for(int k = l; k < r; k++) ans = min(ans, f[l][k] + f[k+1][r] + sum[r] - sum[l-1]); f[l][r] = ans; } } printf("%d ", f[1][n]); return 0; }
V2 复杂度 On2
环形问题可以在后面再接一段数组
int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i]; a[i+n] = a[i]; } for(int i = n+1; i <= 2*n; i++) sum[i] = sum[i-1] + a[i]; for(int i = 0; i <= 2*n; i++) for(int j = 0; j <= 2*n; j++) { if(i == j) f[i][j] = 0, s[i][j] = i; else f[i][j] = INF; } for(int len = 2; len <= n; len++) { for(int l = 1; l <= 2*n-len+1; l++) { int r = l+len-1; for(int k = s[l][r-1]; k <= s[l+1][r]; k++) { int ans = f[l][k] + f[k+1][r] + sum[r] - sum[l-1]; if(ans < f[l][r]) { f[l][r] = ans; s[l][r] = k; } } } } int res = INF; for(int i = 1; i <= n; i++) res = min(res, f[i][i+n-1]); printf("%d ", res); return 0; }
V3 复杂度 Onlogn
HDU 3516
给一堆点，在平面内选择一个位置做根，只能向右和向上连向点，问最小的连线总长度
竟然。。是区间DP问题。。。还要四边形优化
发现把两段合并好的树l~k-1 k~r 再合并在一起需要花费cal
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int SZ = 2100; const int INF = 1e9+10; int a[SZ], sum[SZ], f[SZ][SZ], s[SZ][SZ]; struct node { int x, y; }pos[SZ]; int cal(int l, int k, int r) { int ans = pos[k].x-pos[l].x + pos[k-1].y-pos[r].y; return ans; } int main() { int n; while(~scanf("%d", &n)) { for(int i = 1; i <= n; i++) scanf("%d %d", &pos[i].x, &pos[i].y); for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) { if(i == j) f[i][j] = 0, s[i][j] = i; else f[i][j] = INF; } for(int len = 2; len <= n; len++) { for(int l = 1; l <= n-len+1; l++) { int r = l+len-1; for(int k = s[l][r-1]; k <= s[l+1][r]; k++) { int ans = f[l][k-1] + f[k][r] + cal(l, k, r); if(ans <= f[l][r]) { f[l][r] = ans; s[l][r] = k; } } } } printf("%d ", f[1][n]); } return 0; }
POJ 2955 括号匹配
为什么忘性这么大。。
int f[SZ][SZ], s[SZ][SZ]; int main() { char s[111]; while(1) { scanf(" %s", s+1); if(s[1] == 'e') break; int n = strlen(s)-1; memset(f, 0, sizeof(f)); for(int len = 2; len <= n; len++) for(int l = 1; l <= n-len+1; l++) { int r = l+len-1; if((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']')) f[l][r] = f[l+1][r-1]+2; for(int k = l; k < r; k++) f[l][r] = max(f[l][r], f[l][k] + f[k+1][r]); } printf("%d ", f[1][n]); } return 0; }
LightOJ 1422
题意：每一场Party都要穿相应的衣服，一次可以套着穿多件，如果某两场Party衣服一样，同一件就可以接着用，脱下过的衣服就不能再穿了 ，现在要求最少穿的衣服。
思路： f[i][j] 表示 i-j天里需要的衣服数，考虑区间dp
在l - r天内，若a[l] == a[r] 则第r天可以不穿，f[l][r] = f[l][r-1]
否则第r天要穿，f[l][r] = f[l][r-1]+1
然后枚举l - r之间的k，若a[l] == a[k] 则第k天可以不换，f[l][r] = min(f[l][r], f[l][k-1] + f[k][r])
区间DP的边界问题真的是个玄学orz
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int SZ = 150; int a[SZ], f[SZ][SZ]; int main() { int T, tt = 0; scanf("%d", &T); while(T--) { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); memset(f, 63, sizeof(f)); for(int i = 1; i <= n; i++) f[i][i] = 1; for(int len = 1; len <= n; len++) for(int l = 1; l <= n; l++) { int r = l+len; if(r > n) break; if(a[l] == a[r]) f[l][r] = f[l][r-1]; else f[l][r] = f[l][r-1] + 1; for(int k = l+1; k < r-1; k++) if(a[l] == a[k]) f[l][r] = min(f[l][r], f[l][k-1] + f[k][r]); } printf("Case %d: %d ", ++tt, f[1][n]); } return 0; }