Poj2948Martian Mining(记忆化)

时间:2022-08-04 20:37:37

链接

这题意好难懂 看得迷迷糊糊 想的也迷迷糊糊  后来睡了会突然想到了。。不就是类似以前的矩阵操作

从右下角记忆化   大的由小的推来

dp[i][j] = max(dp[i-1][j]+s1,dp[i][j-1]+s2) s1 = a[i][g]+..a[i][j] s2 = b[g][j]+..b[i][j]

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[][];
int n,m;
int a[][];
int b[][];
int dfs(int i,int j)
{
if(i<||j<)
return ;
if(dp[i][j]!=-)
return dp[i][j];
int g,s1=,s2=;
for(g = ; g <= i ; g++)
s1+=b[g][j];
for(g = ; g <= j ; g++)
s2+=a[i][g];
dp[i][j] = max(dfs(i-,j)+s2,dfs(i,j-)+s1);
return dp[i][j];
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==)
break;
memset(dp,-,sizeof(dp));
for(i = ; i <= n ; i++)
for(j = ; j <= m ; j++)
scanf("%d",&a[i][j]);
for(i = ; i <= n ; i++)
for(j = ; j <= m ; j++)
scanf("%d",&b[i][j]);
int ans = dfs(n,m);
printf("%d\n",ans);
}
return ;
}