区间 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\n", 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\n", 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\n", 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\n", f[1][n]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2735667.html