poj1157 dp

题目链接：http://poj.org/problem?id=1157

题目大意：给 F 种花， V 个花瓶（F <= V）， a[i][j] 为 i 种花插到第 j 个花瓶的价值，要求第 i + 1 种花要在第 i 种花的右边，求最大的价值和。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <map>
 9 #include <vector>
10 using namespace std;
11 
12 int max(int a, int b)
13 {
14     return a > b ? a : b;
15 }
16 int main()
17 {    
18     int m, n, i, j, a[120][120], dp[120][120];
19     while(~scanf("%d %d", &m, &n))
20     {
21         for (i = 1; i <= m; i++)
22         {
23             for(j = 1; j <= n; j++)
24                 scanf("%d", &a[i][j]);
25         }
26         memset(dp, 0, sizeof(dp));
27         for(i = 0; i <= n; i++)
28             dp[0][i] = 0;
29         for(i = 1; i <= m; i++)
30             dp[i][i] = dp[i - 1][i - 1] + a[i][i];
31         for(i = 1; i <= m; i++)
32         {
33             for(j = i + 1; j <= n; j++)
34             {
35                 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + a[i][j]);
36             }
37         }
38         printf("%d
", dp[m][n]);
39     }    
40     return 0;
41 }