NOIP2000 提高组 复赛 方格取数

NOIP2000 提高组 复赛 方格取数

洛谷 P1004 方格取数

//1277 【例9.21】方格取数

//http://blog.csdn.net/yanyanwenmeng/article/details/77073629此文思路代码都写得很不错

//一个笔误，修改了一个多小时，样例通过，提交AC 2017-12-29

#include <stdio.h>

#include <string.h>

int a[15][15],f[15][15][15][15];//f[i][j][r][c];(i,j),(r,c)最大值

int max(int a,int b){

    return a>b?a:b;

}

int main(){

    int i,j,r,c,n,u,v,w,t1,t2;

    scanf("%d",&n);

    memset(a,0,sizeof(a)),memset(f,0,sizeof(f));

    while(scanf("%d%d%d",&u,&v,&w)&&u&&v&&w)a[u][v]=w;

    for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

            for(r=1;r<=n;r++)

                for(c=1;c<=n;c++){

                    t1=max(f[i-1][j][r-1][c],f[i-1][j][r][c-1]);

                    t2=max(f[i][j-1][r-1][c],f[i][j-1][r][c-1]);//此处写成 t1=max(f[i][j-1][r-1][c],f[i][j-1][r][c-1]);昏招尽出，查了一个多小时

                    f[i][j][r][c]=max(t1,t2)+a[i][j];//找 f[i-1][j][r-1][c] f[i-1][j][r][c-1] f[i][j-1][r-1][c] f[i][j-1][r][c-1]中的最大值，顺序可打乱

                    if(i!=r&&j!=c)f[i][j][r][c]+=a[r][c];

                }

    printf("%d",f[n][n][n][n]);

    return 0;

}