数字三角形问题-白红宇

数字三角形问题

阅读量：7229 次

发布时间：2019-06-29

本文共 3653 字，大约阅读时间需要 12 分钟。

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 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
             
               8 #include 
              
                9 10 using namespace std;11 12 #define PI acos(-1.0)13 #define EPS 1e-1014 #define lll __int6415 #define ll long long16 #define INF 0x7fffffff17 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
               
                =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\n",a[0][0]);33 }34 return 0;35 }

View Code

2.数字三角形问题2：

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

•某一层可以随意跳

思路：加一维状态即可。

解法一：

1 #include 
         
           2 #include 
          
            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 long10 #define INF 0x7fffffff11 #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\n",max(dp[1][1],dp[1][0]));52     }53     return 0;54 }

View Code

解法二：

1 #include 
         
           2 #include 
          
            3 #include 
           
             4 #include 
            
              5  6 using namespace std; 7  8 #define PI acos(-1.0) 9 #define EPS 1e-610 #define lll __int6411 #define ll long long12 #define INF 0x7fffffff13 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\n",dp[1][1][1]);40     }41     return 0;42 }