POJ 3176 Cow Bowling

http://poj.org/problem?id=3176

定义dp[i][j] 到这个点能取得的最大值

转移方程

 dp[i][j] = court[i][j] + max(dp[i-1][j-1], dp[i-1][j]);

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 int n;
 9 int court[355][355], dp[355][355];
10 bool OK(int x, int y, int n)
11 {
12     if (x < 0 || x > n || y < 0 || y > n) return false;
13     return true;
14 }
15 
16 //定义dp[i][j] 到达(i, j)这个点 所能取得的最大值
17 int main()
18 {
19     freopen("in.txt", "r", stdin);
20     scanf("%d", &n);
21     for (int i = 0; i < n; i++)
22     {
23         for (int j = 0; j <= i; j++)
24         {
25             scanf("%d", &court[i][j]);
26         }
27     }
28     memset(dp, 0, sizeof(dp));
29     dp[0][0] = court[0][0];
30     for (int i = 1; i < n; i++)
31     {
32         for (int j = 0; j <= i; j++)
33         {
34             if (j == 0) dp[i][j] = court[i][j] + dp[i-1][j];
35             else if (j == i) dp[i][j] = court[i][j] + dp[i-1][j-1];
36             else dp[i][j] = court[i][j] + max(dp[i-1][j-1], dp[i-1][j]);
37         }
38     }
39     sort(dp[n-1], dp[n-1]+n);
40     reverse(dp[n-1], dp[n-1]+n);
41     cout << dp[n-1][0] << endl;
42     return 0;
43 }