数字三角形问题

1.数字三角形问题1：

• 7

• 3 8

• 8 1 0

• 2 7 4 4

•4 5 2 6 5

•从第一层走到最后一层，每次向左下或右下走，求路径的最大权值和。

思路：

•如果利用转移方程求解原问题？

•f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j]

•1、从上向下转移，即i从小到大？

•2、从下向上转移，即i从大到小？

•观察转移方程的性质

•因为第i行的解要由第i+1行的解得到，所以必须从下向上转移！！

代码：

 1 #include <fstream>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <cmath>
 7 #include <cstdlib>
 8 #include <queue>
 9 
10 using namespace std;
11 
12 #define PI acos(-1.0)
13 #define EPS 1e-10
14 #define lll __int64
15 #define ll long long
16 #define INF 0x7fffffff
17 
18 const int N=100;
19 int a[N][N];
20 
21 int main(){
22     //freopen("D:\input.in","r",stdin);
23     //freopen("D:\output.out","w",stdout);
24     int n;
25     while(~scanf("%d",&n)){
26         for(int i=0;i<n;i++)
27             for(int j=0;j<=i;j++)
28                 scanf("%d",&a[i][j]);
29         for(int i=n-2;i>=0;i--)
30             for(int j=0;j<=i;j++)
31                 a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
32         printf("%d
",a[0][0]);
33     }
34     return 0;
35 }

View Code

2.数字三角形问题2：

在问题1的基础上加上一条件：

•某一层可以随意跳

思路：加一维状态即可。

解法一：

 1 #include <fstream>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 #define PI acos(-1.0)
 7 #define EPS 1e-6
 8 #define lll __int64
 9 #define ll long long
10 #define INF 0x7fffffff
11 #define rep(i,a,b) for(int i=a;i<=b;i++)
12 #define dep(i,a,b) for(int i=a;i>=b;i--)
13 
14 int s[102*103/2],dp[102*103/2][2];//dp:从第i点起至最后一层且第i点所在层以后(包括该层)是否跳过的最优值(第二维为1表示已跳过)
15 int n,cnt;
16 
17 int main()
18 {
19     //freopen("D:\input.in","r",stdin);
20     //freopen("D:\output.out","w",stdout);
21     int t,t2,t3;
22     while(scanf("%d",&n)&&n)
23     {
24         cnt=n*(n+1)/2;
25         rep(i,1,cnt)
26         {
27             scanf("%d",s+i);
28             dp[i][0]=0;
29             dp[i][1]=0;
30         }
31         t=n*(n-1)/2;
32         rep(i,1,n)
33         {
34             t2=t+i;
35             dp[t2][0]=s[t2];
36             dp[t2][1]=dp[t2][0];
37         }
38         dep(i,n-1,1)
39         {
40             t=i*(i-1)/2;
41             t2=i*(i+1)/2;
42             t3=0;
43             rep(j,1,i+1)
44                 t3=max(t3,dp[t2+j][0]);
45             rep(j,1,i)
46             {
47                 dp[t+j][0]=s[t+j]+max(dp[t2+j][0],dp[t2+j+1][0]);
48                 dp[t+j][1]=s[t+j]+max(max(dp[t2+j][1],dp[t2+j+1][1]),t3);
49             }
50         }
51         printf("%d
",max(dp[1][1],dp[1][0]));
52     }
53     return 0;
54 }

View Code

解法二：

 1 #include <fstream>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 #define PI acos(-1.0)
 9 #define EPS 1e-6
10 #define lll __int64
11 #define ll long long
12 #define INF 0x7fffffff
13 
14 const int N=100;
15 int a[N][N],dp[N][N][2];//第三维若是1，表示此层之下发生过跳跃。
16 
17 int main()
18 {
19     //freopen("D:\input.in","r",stdin);
20     //freopen("D:\output.out","w",stdout);
21     int n;
22     while(scanf("%d",&n)&&n){
23         for(int i=1;i<=n;i++){
24             for(int j=1;j<=i;j++){
25                 scanf("%d",&a[i][j]);
26             }
27         }
28         memset(dp,0,sizeof(dp));
29         for(int i=1;i<=n;i++)   dp[n][i][0]=a[n][i],dp[n][i][1]=a[n][i];
30         for(int i=n-1;i>0;i--){
31             int maxn=0;
32             for(int j=1;j<=i+1;j++)
33                 if(dp[i+1][j][0]>maxn)  maxn=dp[i+1][j][0];
34             for(int j=1;j<=i;j++){
35                 dp[i][j][0]=a[i][j]+max(dp[i+1][j][0],dp[i+1][j+1][0]);
36                 dp[i][j][1]=a[i][j]+max(max(dp[i+1][j][1],dp[i+1][j+1][1]),maxn);
37             }
38         }
39         printf("%d
",dp[1][1][1]);
40     }
41     return 0;
42 }

View Code

样例：

4
1
3 2
4 10 1
4 3 2 20
0

answer：34