POJ_3176_Cow_Bowling(数字三角形)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using std :: max;
 5 
 6 const int maxn=355;
 7 int a[maxn][maxn],f[maxn][maxn];
 8 int n;
 9 
10 int dfs(int i,int j)
11 {
12     if(f[i][j]!=-1) return f[i][j];
13     if(i==n) return f[i][j]=a[i][j];
14     return f[i][j]=a[i][j]+max(dfs(i+1,j),dfs(i+1,j+1));
15 }
16 
17 void init()
18 {
19     scanf("%d",&n);
20     for(int i=1;i<=n;i++)
21     {
22         for(int j=1;j<=i;j++)
23         {
24             scanf("%d",&a[i][j]);
25         }
26     }
27     memset(f,-1,sizeof(f));
28 }
29 
30 int main()
31 {
32 #ifndef ONLINE_JUDGE
33     freopen("cow.in","r",stdin);
34     freopen("cow.out","w",stdout);
35 #endif
36     init();
37     printf("%d\n",dfs(1,1));
38 #ifndef ONLINE_JUDGE
39     fclose(stdin);
40     fclose(stdout);
41 #endif
42     return 0;
43 }

 1 #include<cstdio>
 2 #include<algorithm>
 3 using std :: max;
 4 
 5 const int maxn=355;
 6 int n;
 7 int a[maxn][maxn],f[maxn][maxn];
 8 
 9 void solve()
10 {
11     for(int i=n-1;i>=1;i--)
12     {
13         for(int j=1;j<=i;j++)
14         {
15             f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
16         }
17     }
18     printf("%d\n",f[1][1]);
19 }
20 
21 void init()
22 {
23     scanf("%d",&n);
24     for(int i=1;i<=n;i++)
25     {
26         for(int j=1;j<=i;j++)
27         {
28             scanf("%d",&a[i][j]);
29         }
30     }
31     for(int j=1;j<=n;j++) f[n][j]=a[n][j];
32 }
33 
34 int main()
35 {
36 #ifndef ONLINE_JUDGE
37     freopen("cow.in","r",stdin);
38     freopen("cow.out","w",stdout);
39 #endif
40     init();
41     solve();
42 #ifndef ONLINE_JUDGE
43     fclose(stdin);
44     fclose(stdout);
45 #endif
46     return 0;
47 }