和2000的方格取數(shù)如出一轍.數(shù)據(jù)加強(qiáng)了一點(diǎn)，如果是裸的四維dp可能會(huì)超時(shí)(80).所以需要優(yōu)化.
1.普通的四維做法
【狀態(tài)】f[x1][y1][x2][y2] 表示從出發(fā)點(diǎn)分別到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示該格的數(shù).
【方程】f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重復(fù))
【一個(gè)重要優(yōu)化】顯然有y2=x1+y1-x2(y2>0),因而時(shí)間復(fù)雜度可以降到O(n^3).Cena顯示總用時(shí)從近4s降到近0.3s，效果明顯.
2.三維做法(參考官方題解)
【狀態(tài)】f[p][x1][x2],p表示經(jīng)過的格子數(shù).
【方程】f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重復(fù))
未編程驗(yàn)證.
3.更優(yōu)化的做法
dy神牛指出，進(jìn)一步的優(yōu)化需要用到最小費(fèi)用最大流.(NOIP絕對(duì)超綱,可以確定不會(huì)更深了.)
【Code】
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[52][52][52][52] = {0}, n, G[52][52];
5 int max(int a, int b, int c, int d){
6 if (a < b) a= b;
7 if (a < c) a= c;
8 if (a < d) a= d;
9 return a;
10 }
11 int main(){
12 int m, n, i, j, k, l;
13 scanf("%d%d", &m, &n);
14 for (i = 1; i <= m; i++)
15 for (j = 1; j <= n; j++)
16 scanf("%d", &G[i][j]);
17 for (i = 1; i <= m; i++)
18 for (j = 1; j <= n; j++)
19 for (k = 1; k <= m; k++){
20 if (i+j-k > 0) l = i+j-k; else continue;
21 f[i][j][k][l] = max(f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1])+G[i][j]+G[k][l];
22 if (i == k && j == l) f[i][j][k][l] -= G[i][j];
23 }
24 printf("%d\n", f[m][n][m][n]);
25 }
26