摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : DP

有更好的3維作法  請大家自行搜尋

/***********************************************************/

#include<stdlib.h>
#include<stdio.h>
int N,M;
int map[51][51];
short f[51][51][51][51];
main()
{
    scanf("%d %d",&N,&M);
       {
           int a,b,c;
           for(a=1;a<=N;a++)
               for(b=1;b<=M;b++)
                  scanf("%d",&map[a][b]);
           int i,j,x,y;
           for(i=1;i<=N;i++)
              for(j=1;j<=M;j++)
                 for(x=1;x<=N;x++)
                    for(y=1;y<=M;y++)
                        {
                          int MAX;
                          MAX=(f[i-1][j][x-1][y]>f[i-1][j][x][y-1])?f[i-1][j][x-1][y]:f[i-1][j][x][y-1];
                          MAX=(MAX>f[i][j-1][x][y-1])?MAX:f[i][j-1][x][y-1];
                          MAX=(MAX>f[i][j-1][x-1][y])?MAX:f[i][j-1][x-1][y];
                         f[i][j][x][y]+=map[i][j]+MAX;                              
                          if(i!=x||j!=y)
                             f[i][j][x][y]+=map[x][y];
                        }
           printf("%d\n",f[N][M][N][M]);
       }
  return 0;
}
/*
f[i][j][x][y]表示第一路到（i，j)，第二路到(x，y)的好心度最大值。
*/