51nod oj 1084 矩阵取数问题 V2 【双回路矩阵DP】

题目链接：1084

具体解析请看：这里

代码：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int shu[220][220]; int dp[420][220][220]; int main() { int n,m; scanf("%d%d",&m,&n); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&shu[i][j]); memset(dp,0,sizeof(dp)); dp[1][1][2]=shu[1][1]+shu[1][2]+shu[2][1]; for (int i=2;i<n+m-2;i++) { for (int j=max(1,i-n+2);j<=min(m-1,i);j++) { for (int k=j+1;k<=min(m,i+1);k++) { dp[i][j][k]=max(max(dp[i-1][j-1][k-1],dp[i-1][j-1][k]),max(dp[i-1][j][k-1],dp[i-1][j][k]))+shu[i+2-j][j]+shu[i+2-k][k]; } } } int ans=dp[n+m-3][m-1][m]+shu[n][m]; printf("%d\n",ans); return 0; }