http://acm.pku.edu.cn/JudgeOnline/problem?id=1157
Код:
#include<stdio.h> int main() { int f,v; int i,j,max; int a[200][200]; long w[200][200]; w[0][0]=0; scanf("%d%d",&f,&v); for(i=1;i<=f;i++) for(j=1;j<=v;j++) scanf("%d",&a[i][j]); for(i=1;i<=v;i++) w[1][i]=a[1][i]; for(i=2;i<=f;i++) { w[i][i-1]=-2500; for(j=i;j<=v-f+i;j++) { w[i][j]=-2500; if (w[i][j-1]-a[i][j-1]+a[i][j]>w[i][j]) w[i][j]=w[i][j-1]+a[i][j]-a[i][j-1]; if (w[i-1][j-1]+a[i][j]>w[i][j]) w[i][j]=w[i-1][j-1]+a[i][j]; } } max=-2500; for(j=f;j<=v;j++) if(w[f][j]>max) max=w[f][j]; printf("%ld\n",max); return 0; }