hdu2829：
dp方程：f[m][n] = Min{f[m-1][k]+w[k+1][n]}。
令w[i][j](i<=j)表示(a[i]*a[i+1]+a[i]*a[i+2]+....+a[i]*a[j])+(a[i+1]*a[i+2]+a[i+1]=a[i+3]+....)+....+a[j-1]*a[j]——(1)
则(1)式可以表示为[(a[i]+a[i+1]+...+a[j])*(a[i]+a[i+1]+...+a[j])-a[i]^2-a[i+1]^2-....-a[j]^2] / 2
即(1) = [(sum1[j]-sum1[i-1])^2-(sum2[j]-sum2[i-1])]/2。
其中sum1[i]表示从0到i元素的和，sum2[i]表示从0到i元素的平方的和，可以用O(n)的时间预处理。
现在我们固定j，看一看函数 w[i][j+1]-w[i][j] 随i增加的增减性，很明显如果i加1的话，w[i][j+1]比w[i][j]减少的要多，所以该函数递减，所以w为凸；
而区间包含关系是很显然的，所以w函数满足四边形不等式，所以可以推得f[m][n]也满足四边形不等式。
决策变量范围：s[m-1][n]<=s[m][n]<=s[m][n+1]。实际上这个地方的单调性凭感觉也是很好发现的，试想一下，如果你亲自去划分（而不是程序去划分）的话，你也会这么做的。
#include#include #include usingnamespace std; constint N =1010; typedef longlong llg; int n, m, a[N], sum1[N], sum2[N], s[N][N]; llg f[N][N]; void dp() { int i, j, k, a, b; llg tmp; memset(f, -1, sizeof(f)); for(i =0; i <= n; i++) { tmp = sum1[i]; f[0][i] = (tmp*tmp - sum2[i]) /2; s[0][i] =0; } for(i =1; i <= m; i++) for(j = n; j >= i; j--) { s[i][n+1] = n; a = s[i-1][j]; b = s[i][j+1]; for(k = a; k <= b; k++) { tmp = sum1[j] - sum1[k]; tmp = f[i-1][k]+(tmp*tmp - (sum2[j]-sum2[k])) /2; if(f[i][j]==-1|| f[i][j]>tmp) { f[i][j] = tmp; s[i][j] = k; } } } } int main() { int i; while(scanf("%d%d", &n, &m) != EOF) { if(n==0&& m==0) break; sum1[0] = sum2[0] =0; for(i =1; i <= n; i++) { scanf("%d", a+i); sum1[i] = sum1[i-1] + a[i]; sum2[i] = sum2[i-1] + a[i]*a[i]; } dp(); printf("%lld\n", f[m][n]); } return0; }
hdu3480：
需要先排一下序，dp方程和上面一个题差不多，就是w不同，w[i][j] = (a[j]-a[i])*(a[j]-a[i])
然后w函数的区间包含关系是很显然的，然后对于w[i][j+1]-w[i][j]，固定j，很明显由于平方关系w[i][j+1]减小的比较快，所以单调递减；所以满足凸特性，所以满足四边形不等式。。所以。。。贴代码～～注意需要滚动数组，要不用long long会MLE的，即使内存给的很大。。
#include#include #include #include usingnamespace std; constint N =10010; constint M =5010; typedef longlong llg; int n, m, flag, s[2][N]; llg a[N], f[2][N]; void dp() { int i, j, k, head, tail; flag =1; llg tmp; memset(f, -1, sizeof(f)); for(i =1; i <= n; i++) { f[flag][i] = (a[i]-a[1])*(a[i]-a[1]); s[flag][i] =0; } flag ^=1; for(i =2; i <= m; i++) { s[flag][n+1] = n; for(j =1; j <= n; j++) f[flag][j] =-1; for(j = n; j >= i; j--) { head = s[flag^1][j]; tail = s[flag][j+1]; for(k = head; k <= tail; k++) { tmp = (a[j]-a[k+1])*(a[j]-a[k+1]); if(f[flag][j]==-1|| f[flag][j]>f[flag^1][k]+tmp) { f[flag][j] = f[flag^1][k] + tmp; s[flag][j] = k; } } } flag ^=1; } } int main() { int t, i, Case =0; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); if(m > n) m = n; for(i =1; i <= n; i++) scanf("%lld", a+i); sort(a+1, a+n+1); dp(); printf("Case %d: %lld\n", ++Case, f[flag^1][n]); } return0; }
hdu3516：
这个题看起来很像石子合并最小得分，但是却和石子合并不同，石子合并的w[i][j]值是恒定的，而这个题的w[i][j]却随决策变量k的不同而不同。所以这个题不能用贪心，需要用dp。
dp方程：f[i][j] = f[i][k]+f[k+1][j] + w[i][j]
但是这里有个问题，w[i][j]的取值和决策k是有关系的，不能直接看出是否满足四边形不等式。
可以这么想：如果我们固定k，由于w[i][j] = p[k+1].x-p[i].x+p[k].y-p[j].y，所以固定j时，w[i][j+1]-w[i][j] = (p[k+1].x-p[i].x+p[k].y-p[j].y) - (p[k+1].x-p[i].x+p[k].y-p[j+1].y) = (-p[j].y)-(-p[j+1].y) = p[j+1].y - p[j].y < 0 == c（因为题意说明：p[j+1].y严格小于p[j].y）。所以对于所有决策k，w[i][j+1]-w[i][j]随i增加始终是个常数，当然也可以说成是非递增或这说是不严格递减，所以可以认为w[i][j]是凸的；区间包含关系显而易见。所以综上，w[i][j]对于所有决策k均满足四边形不等式，所以f[i][j]也满足四边形不等式，所以可以到处决策单调性：s[i][j-1]<=s[i][j]<=s[i+1][j]。
View Code #include#include #include #include usingnamespace std; constint N =1010; struct node { int x, y; }p[N]; int n, f[N][N], s[N][N]; bool cmp(const node &a, const node &b) { return a.x < b.x; } void dp() { int i, l, j, k, tmp; for(i =1; i <= n; i++) { f[i][i] =0; s[i][i] = i; } for(l =1; l < n; l++) for(i =1; i+l <= n; i++) { j = i+l; f[i][j] =-1; for(k = s[i][j-1]; k <= min(s[i+1][j], j-1); k++) { tmp = p[k+1].x-p[i].x+p[k].y-p[j].y; if(f[i][j]==-1|| f[i][j]>f[i][k]+f[k+1][j]+tmp) { s[i][j] = k; f[i][j] = f[i][k] + f[k+1][j] + tmp; } } } } int main() { int i; while(scanf("%d", &n) != EOF) { for(i =1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y); sort(p+1, p+n+1, cmp); dp(); printf("%d\n", f[1][n]); } return0; }
pku1160：
跟前该帖子描述的前两个dp是差不多的，这个题目我觉得比较巧的地方是预处理。
res[i][j] = res[i][j-1]+a[j]-a[mid]
为什么可以这么递推呢？因为区间(i,j)和区间(i,j+1)可以使用同一个中位数。因为这两个里面必然有一个区间长度为偶数，对于偶数长度来说，在该题中中间两个值都可以作为中位数，加入某一边扩展一点变成奇数长度的话，则取相应的靠近那一边的中间那个数当中位数就行啦。
View Code #include#include #include #include usingnamespace std; constint N =310; typedef longlong llg; int n, m, a[N], s[36][N], f[36][N], res[N][N]; void dp() { int i, j, k, a, b, tmp; memset(f, -1, sizeof(f)); f[1][0] =0; for(i =1; i <= n; i++) { f[1][i] = res[1][i]; s[1][i] =0; } for(i =2; i <= m; i++) { s[i][n+1] = n; for(j = n; j >= i; j--) { a = s[i-1][j]; b = s[i][j+1]; for(k = a; k <= min(b,j-1); k++) { tmp = res[k+1][j]; if(f[i][j]==-1|| f[i][j]>f[i-1][k] + tmp) { s[i][j] = k; f[i][j] = f[i-1][k] + tmp; } } } } } int main() { int i, j, mid; scanf("%d%d", &n, &m); if(m > n) m = n; for(i =1; i <= n; i++) scanf("%d", a+i); a[0] =0; sort(a, a+n+1); for(i =1; i <= n; i++) { res[i][i] =0; for(j = i+1; j <= n; j++) { mid = (i+j) >>1; res[i][j] = res[i][j-1] + a[j] - a[mid]; } } dp(); printf("%d\n", f[m][n]); return0; }