基准时间限制：2 秒 空间限制：131072 KB 分值: 80
一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。
例如：3 * 3的方格。
1 3 3
2 1 3
2 2 1
能够获得的最大价值为：17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起点和终点的奖励只计算1次。
Input
第1行：2个数M N，中间用空格分隔，为矩阵的大小。(2 <= M, N <= 200)第2 - N + 1行：每行M个数，中间用空格隔开，对应格子中奖励的价值。(1 <= A[i,j] <= 10000)
Output
输出能够获得的最大价值。
Input示例
3 31 3 32 1 32 2 1
Output示例
17 // 读数真是会玩， 首先说是 M * N 的矩阵，然后读入是 m， n ，然而，却是 n 行 m 列 //其实仔细分析一下这个问题可知，就是从起点走两条线向终点，然后可以想到，其实两段线并不会相交，因为如果相交，必定存在一个不相交的方案使和更大。 dp[st][a][b] 表示，走 st 步，第一条线在 a 行， 第二条线在 b 行，各自的列数可以计算出，然后就分四种情况愉快的dp辣 DP:
1 #include2 using namespace std; 3 #define MOD 998244353 4 #define INF 0x3f3f3f3f 5 #define LL long long 6 #define MX 205 7 8 int m, n; 9 int dat[MX][MX];10 int dp[MX*2][MX][MX]; //step , a , b11 12 int main()13 {14 while (scanf("%d%d",&m,&n)!=EOF)15 {16 for (int i=1;i<=n;i++)17 {18 for (int j=1;j<=m;j++)19 scanf("%d",&dat[i][j]);20 }21 int ut = n+m-2;22 for (int st=ut;st>=0;st--)23 {24 for (int a=1;a<=n;a++)25 {26 for (int b=1;b<=a;b++)27 {28 int ay = st-a+2;29 int by = st-b+2;30 if (ay<1||ay>n||by<1||by>n) continue;31 32 int tp1 = max(dp[st+1][a+1][b+1],dp[st+1][a][b]);33 int tp2 = max(dp[st+1][a+1][b], dp[st+1][a][b+1]);34 tp1 = max(tp1,tp2);35 if (a==b)36 dp[st][a][b] = max(dp[st][a][b],tp1 + dat[a][ay]);37 else38 dp[st][a][b] = max(dp[st][a][b],tp1 + dat[a][ay] + dat[b][by]);39 //printf("?:%d %d %d %d\n",st,a,b,dp[st][a][b]);40 }41 }42 }43 printf("%d\n",dp[0][1][1]);44 }45 return 0;46 }
最小费用最大流也可做，正好学习一下