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;
}