rqnoj/314.c

   1 #include <stdio.h>
   2
   3 #define maxn 11
   4 #define max(p,q) ((p)>(q)?(p):(q))
   5
   6 int a[maxn][maxn],f[maxn][maxn][maxn][maxn]={0};
   7
   8 int main()
   9 {
  10         int n,i,j;
  11         scanf("%d",&n);
  12         int x,y,value;
  13         scanf("%d%d%d",&x,&y,&value);
  14         while ((x!=0) && (y!=0) && (value!=0))
  15         {
  16                 a[x][y]=value;
  17                 scanf("%d%d%d",&x,&y,&value);
  18         }
  19         int p,q;
  20         f[1][1][1][1]=a[1][1];
  21         for (i=1; i<=n; i++)
  22                 for (j=1; j<=n; j++)
  23                         for (p=1; p<=n; p++)
  24                                 for (q=1; q<=n; q++)
  25                                         if (!(i==p && j==q) || (i==n && j==n))
  26                                         {
  27                                                 f[i][j][p][q]=max(f[i-1][j][p][q-1],f[i][j][p][q]);
  28                                         f[i][j][p][q]=max(f[i-1][j][p-1][q],f[i][j][p][q]);
  29                                             f[i][j][p][q]=max(f[i][j-1][p-1][q],f[i][j][p][q]);
  30                                         f[i][j][p][q]=max(f[i][j-1][p][q-1],f[i][j][p][q]);
  31                                             f[i][j][p][q]+=a[i][j]+a[p][q];
  32                                         }
  33         printf("%d\n",f[n][n][n][n]-a[n][n]);
  34         return 0;
  35 }