动态规划
d[i][j]表示到达该点时的最大金币数。
按列进行DP可以防止走重复的格子
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include <cmath> #include<algorithm> #include<stack> using namespace std; int T; int n,m; int a[110][110]; int d[110][110]; void input() { memset(d,-111,sizeof(d)); // cout<<d[0][0]<<" "; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { cin>>a[i][j]; // d[i][j]=a[i][j]; // cout<<a[i][j]<<" "; } // cout<<endl; } } void dp() { d[0][0]=a[0][0]; for(int i=1;i<m;i++) { d[i][0]=d[i-1][0]+a[i][0]; } // for(int i=0;i<m;i++) cout<<d[i][0]<<" "; for(int j=1;j<n;j++) { for(int i=0;i<m;i++) { int tmp=a[i][j]; d[i][j]=max(d[i][j],a[i][j]+d[i][j-1]); for(int k=i-1;k>=0;k--) { tmp+=a[k][j]; d[i][j]=max(d[i][j],tmp+d[k][j-1]); } tmp=a[i][j]; for(int k=i+1;k<m;k++) { tmp+=a[k][j]; d[i][j]=max(d[i][j],tmp+d[k][j-1]); //if (i==0) cout<<d[i][j]<<" "; } } // cout<<endl; } } int main() { // freopen("input.txt","r",stdin); scanf("%d",&T); for(int i=1;i<=T;i++) { scanf("%d %d",&m,&n); input(); dp(); printf("Case #%d:\n",i); printf("%d\n",d[0][n-1]); } return 0; }