比赛 清明时节雨纷纷,今天天气很晴朗 评测结果 AAAAAAAAAA
题目名称 传纸条 最终得分 100
用户昵称 Hyoi_deque 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2017-04-07 19:37:01
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int a[55][55];
int N,M;
int f[200][55][55];
int Main(){
    freopen("message.in","r",stdin);
	freopen("message.out","w",stdout);
    scanf("%d%d",&M,&N);
    for(int i=1;i<=M;i++){
        for(int j=1;j<=N;j++){
            scanf("%d",&a[i][j]);
        }
    }

    for(int step=1;step<=M+N-3;step++){
        int l,r;
        if(step<=M-1) l=1,r=1+step;
        else l=step-M+2,r=N;
        for(int x1=l;x1<=r;x1++){
            int y11=step+2-x1;
            for(int x2=x1+1;x2<=r;x2++){
                int y2=step+2-x2;
            
                int from1=f[step-1][x1][x2];
                int from2=f[step-1][x1-1][x2];
                int from3=f[step-1][x1][x2-1];
                int from4=f[step-1][x1-1][x2-1];
                int delta=a[y11][x1]+a[y2][x2]; 
                if(x2==x1+1){
                    f[step][x1][x2]=max(from1,max(from2,from4))+delta;
                }
                else if(x2>x1+1){
                    f[step][x1][x2]=max(from1,max(from2,max(from3,from4)))+delta;
                }    
            }
        }
    }
    cout<<f[N+M-3][N-1][N];
    return 0;
}
int work=Main();
 int main(){;
 }