# Cow Bowling POJ 3176(基础dp)

## 代码

``` 1 #include <iostream>
2 #include <algorithm>
3 #include <utility>
4 #include <cstdio>
5 #include <cmath>
6 #include <cstring>
7 #include <string>
8 #include <vector>
9 #include <stack>
10 #include <queue>
11 #include <map>
12 #include <set>
13
14 using namespace std;
15 typedef long long LL;
16 const int INF_INT=0x3f3f3f3f;
17 const LL INF_LL=0x3f3f3f3f3f3f3f3f;
18
19 int dp[400][400];
20 int graph[400][400];
21
22 int main()
23 {
24 //    freopen("black.in","r",stdin);
25 //    freopen("black.out","w",stdout);
26     int n;
27     cin>>n;
28     for(int i=1;i<=n;i++)
29     for(int j=1;j<=i;j++)
30     cin>>graph[i][j];
31     dp[1][1]=graph[1][1];
32     for(int i=2;i<=n;i++)
33     for(int j=1;j<=i;j++)
34     {
35         if(j==1) dp[i][j]=dp[i-1][j]+graph[i][j];
36         else if(j==i) dp[i][j]=dp[i-1][j-1]+graph[i][j];
37         else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+graph[i][j];
38     }
39     int maxn=0;
40     for(int i=1;i<=n;i++) maxn=max(maxn,dp[n][i]);
41     cout<<maxn<<endl;
42
43     return 0;
44 } ```