【问题描述】
背景 Background
JerryZhou同学经常改编习题给自己做。
这天，他又改编了一题。。。。。
【描述 Description】
设有N*N的方格图，我们将其中的某些方格填入正整数，
而其他的方格中放入0。
某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。
在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。
【输入格式 Input Format】
第一行:N (4<=N<=20) 接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0 【输出格式 Output Format】 一行，表示最大的总和。 【样例输入 Sample Input】 4 1 2 3 4 2 1 3 4 1 2 3 4 1 3 2 4 样例输出 Sample Output 39 注释 Hint 多进程DP 算法分析 可以用网络流来做 由于没做二取方格数；我一开始用一般DP；DP一次则把走过的路删去；3次DP； 只对了一组；看了题解后知道了我的算法虽然保证了3次DP的最优；但并不代表全局最优；是有反例的...... 其实可以用压缩数组的方法..因为每一阶段都只与上一阶段有关..滚动滚动数组..循环利用..不断再生..节约环保..{好像扯远了...-_-#}..不过节约时间起见..其实不用滚动数组也可以以0ms过掉.. 做这条题时很深刻地感受得到..这条题是斜着划分阶段的..太伟大了啦..而且由于每一阶段中..横坐标与纵坐标有一种莫名的内在关系..所以为数组节约了不少维..{不过就算不节约..N<=20..也应该不会超..}.. 用sum[k,x,y,z]表示当走到第K步时,且三人横坐标分别为X,Y,Z时..所取数的最大值..由于每一个人都可以由2个方向推来..所以一共有2^3=8种状态.. sum[k,x,y,x]=max(sum[k,x,y,z],sum[k-1,x+f[i,1],y+f[i,2],z+f[i,3]]) 且由于第K步只能到达横坐标<=min(k,n)的点..所以其实循环时可以节约节约.. 注意:每一格只能取一次..数组的大小.. 【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <stdio.h> #include <string.h> #define max(a,b) a>b?a:b int min(int a, int b) { if (a < b) return a; else return b; } int f[41][21][21][21], a[21][21]; int main() { int n, i , j, k, x1, x2, x3, temp, s1, s2, s3; scanf("%d", &n); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) scanf("%d", &a[i][j]); } memset(f, 0, sizeof(f)); f[1][1][1][1] = a[1][1]; for (k = 2; k <= n + n -1; k++) { for (x1 = 1; x1 <= min(k, n); x1++) { for (x2 = 1; x2 <= min(k, n); x2++) { for (x3 = 1; x3 <= min(k, n); x3++) { temp = a[k - x1 + 1][x1] + a[k - x2 + 1][x2] + a[k - x3 + 1][x3]; if (x1 == x2) temp -= a[k - x1 + 1][x1]; if (x1 == x3) temp -= a[k - x1 + 1][x1]; if (x2 == x3) temp -= a[k - x2 + 1][x2]; if (x1 == x2 && x1 == x3) temp += a[k - x1 + 1][x1]; for (s1 = -1; s1 <= 0; s1++) { for (s2 = -1; s2 <= 0; s2++) { for (s3 = -1; s3 <= 0; s3++) { f[k][x1][x2][x3] = max(f[k][x1][x2][x3], f[k - 1][x1 + s1][x2 + s2][x3 + s3] + temp); } } } } } } } printf("%d\n", f[n + n - 1][n][n][n]); return 0; } |