noip08 年的题 看了看题解
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 int f[51][51][51][51]; 5 int a[51][51]; 6 int n,m; 7 int main() 8 { 9 cin>>n>>m; 10 for(int i=1;i<=n;i++) 11 { 12 for(int j=1;j<=m;j++) 13 { 14 cin>>a[i][j]; 15 } 16 } 17 for(int i=1;i<=n;i++) 18 { 19 for(int j=1;j<=m;j++) 20 { 21 for(int k=1;k<=n;k++) 22 { 23 for(int l=1;l<=m;l++) 24 { 25 f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]); 26 f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k-1][l]); 27 f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l-1]); 28 f[i][j][k][l]+=(a[i][j]+a[k][l]); 29 if(i==k&&j==l) 30 { 31 f[i][j][k][l]-=a[i][j]; 32 } 33 } 34 } 35 } 36 } 37 cout<<f[n][m][n][m]; 38 }
//刷了两个多进程的题 然鹅都不会......
关键是设计方程，深刻理解多进程的实现方式以及一切dp题的通用题解（由于所有状态我们都遍历了）