ZSTU2545-地道战

http://acmpj.zstu.edu.cn/JudgeOnline/showproblem?problem_id=2545

呵呵。。。呵呵。。。呵呵。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(void)
{int n,m,i,j,k,g,dp[120][120],x[120][120],y[120][120];while(scanf("%d%d",&n,&m)!=EOF){memset(dp,100000,sizeof(dp));memset(x,100000,sizeof(x));memset(y,100000,sizeof(y));for(i=1;i<=n;i++)for(j=1;j<=m-1;j++)scanf("%d",&x[i][j]);for(i=1;i<=m;i++)for(j=1;j<=n-1;j++)scanf("%d",&y[j][i]);for(i=1;i<=n;i++)for(j=1;j<=m;j++)dp[i][j]=0;g=n>m?n:m;for(i=2;i<=g;i++){k=i+1;for(j=i;j>=1;j--)dp[j][k-j]=min((dp[j][k-j-1]+x[j][k-j-1]),(dp[j-1][k-j]+y[j-1][k-j]));}for(i=2;i<=g;i++){k=i+g;for(j=i;j<=g;j++)dp[k-j][j]=min((dp[k-j][j-1]+x[k-j][j-1]),(dp[k-j-1][j]+y[k-j-1][j]));}printf("%d\n",dp[n][m]);}   return 0;
}