⇤ ← 于2008-11-05 14:45:44修订的的版本1
613
备注:
|
1550
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 46: | 行号 46: |
{{{ #!cplusplus //非递规 #include <stdio.h> #include <memory.h> int tower[102][102]; int tmax[102][102]; int max(int &a, int &b){ return a>b?a:b; } int main(){ int Case; scanf("%d",&Case); while(Case--){ int tHeight; scanf("%d", &tHeight); for(int i = 1; i <= tHeight; i++){ for(int j = 1; j <= i; j++){ scanf("%d", &tower[i][j]); } } memset(tmax,0,101*101*4); //dp for(int k = tHeight; k > 0; k--){ for(int l = 1; l <= k; l++) if(k==tHeight) tmax[k][l] = tower[k][l]; else tmax[k][l] = tower[k][l] + max(tmax[k+1][l],tmax[k+1][l+1]); } printf("%d\n", tmax[1][1]); } return 0; } }}} |
1 #include <iostream>
2 using namespace std;
3 const int N=110;
4 int a[N][N];
5 int f[N][N];
6 int n;
7 void Init()
8 {
9 scanf("%d",&n);
10 for(int i=0;i<n;i++)
11 for(int j=0;j<=i;j++)
12 scanf("%d",&a[i][j]);
13 memset(f,-1,sizeof(f));
14 }
15 int DP(int i,int j)
16 {
17 int ans;
18 if(f[i][j]>=0)
19 return f[i][j];
20 if(i==n-1)
21 ans=a[i][j];
22 else
23 {
24 if(DP(i+1,j)>DP(i+1,j+1))
25 ans=a[i][j]+DP(i+1,j);
26 else
27 ans=a[i][j]+DP(i+1,j+1);
28 }
29 f[i][j]=ans;
30 return f[i][j];
31 }
32 int main()
33 {
34 int test;
35 cin>>test;
36 while(test-->0)
37 {
38 Init();
39 printf("%d\n",DP(0,0));
40 }
41 }
1 //非递规
2 #include <stdio.h>
3 #include <memory.h>
4
5 int tower[102][102];
6 int tmax[102][102];
7
8 int max(int &a, int &b){
9 return a>b?a:b;
10 }
11
12 int main(){
13 int Case;
14 scanf("%d",&Case);
15 while(Case--){
16 int tHeight;
17 scanf("%d", &tHeight);
18 for(int i = 1; i <= tHeight; i++){
19 for(int j = 1; j <= i; j++){
20 scanf("%d", &tower[i][j]);
21 }
22 }
23 memset(tmax,0,101*101*4);
24
25 //dp
26 for(int k = tHeight; k > 0; k--){
27 for(int l = 1; l <= k; l++)
28 if(k==tHeight)
29 tmax[k][l] = tower[k][l];
30 else
31 tmax[k][l] = tower[k][l] + max(tmax[k+1][l],tmax[k+1][l+1]);
32 }
33 printf("%d\n", tmax[1][1]);
34 }
35
36
37 return 0;
38 }