数字三角形系列-白红宇

数字三角形系列

阅读量：5809 次

发布时间：2019-06-18

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

P1044 数字三角形

时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

09年 USACO 11月月赛铜牌第一道

描述

示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路

径，使该路径所经过的数字的总和最大。

　　每一步可沿左斜线向下或右斜线向下走；

　　1<三角形行数<25；

　　三角形中的数字为整数<1000；

输入格式

第一行为N，表示有N行

后面N行表示三角形每条路的路径权

输出格式

路径所经过的数字的总和最大的答案

测试样例1

输入

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出

30

备注

搜索80分，记忆化搜索AC

　　记忆化搜索，从后往前访问。对于每一个点正常往下走时有两种不同走法，于是从上往下走时只需逆推即可。所以对于a[i][j]而言，只需加上a[i+1][j]与a[i+1][j+1]中的最大值。不断循环最后得到最大值为a[1][1]。

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 using namespace std; 6 int a[30][30],n; 7 int main() 8 { 9     cin>>n;10     for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)scanf("%d",&a[i][j]);11     for(int i=n-1;i>=0;i--)12     {13         for(int j=1;j<=i;j++)14         { 15               a[i][j]+=max(a[i+1][j+1],a[i+1][j]); 16         }17     }18     cout<
            
             <

P1076 数字三角形2

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

数字三角形

要求走到最后mod 100最大

输入格式

第1行n，表示n行 <=25

第2到n+1行为每个的权值

输出格式

mod 100最大值

测试样例1

输入

2

1

99 98

输出

99

　　这题tyvj的数据非常诡异，想骗分的朋友输出99会发现自己奇妙的得了90分。

由于数据比较弱所以搞个奇怪的dfs就AC了。

1 #include
            
              2 #include
             
               3 #include
              
                4 #include
               
                 5 using namespace std; 6 int a[30][30],n,ans=0; 7 void dfs(int x,int y,int sum){ 8     if(x==n){ 9         if(sum==99){10             ans=99;11             return;12         }13         else{14             ans=max(ans,sum);15             return;16         }17     }18     dfs(x+1,y,(sum+a[x+1][y])%100);19     dfs(x+1,y+1,(sum+a[x+1][y+1])%100);20 }21 int main()22 {23     memset(a,0,sizeof(a));24     scanf("%d",&n);25     for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)scanf("%d",&a[i][j]);26     dfs(1,1,a[1][1]);27     cout<
                
                 <

View Code

P1079 数字三角形3

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

数字三角形必须经过某一个点，使之走的路程和最大

输入格式

第1行n，表示n行 <=25

第2到n+1行为每个的权值

程序必须经过n div 2,n div 2这个点

输出格式

最大值

测试样例1

输入

2

1

1 1

输出

2

备注

各个测试点1s

　　刚看的时候想做成2段的BFS，后来看题解发现了另一种有趣的做法。

由于必须经过n div 2,n div 2这个点，则可以把这个点的权值加上一个极大的数保证必过，最后输出的时候减去加上的数的大小即可。

1 #include
             
               2 #include
              
                3 #include
               
                 4 #include
                
                  5 using namespace std; 6 int a[30][30],n,ans=0,QAQ; 7 int Max(int x,int y) 8 { 9     if(x>y)return x;10     else return y;11 }12 int main()13 {14     memset(a,0,sizeof(a));15     scanf("%d",&n);16     QAQ=n/2;17     for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)scanf("%d",&a[i][j]);18     a[QAQ][QAQ]+=99999;19     for(int i=n-1;i>=0;i--)20     {21         for(int j=1;j<=i;j++)22         {23             a[i][j]+=Max(a[i+1][j],a[i+1][j+1]);24         }25     }26     cout<
                 
                  <

加权值的做法√

P1084 数字三角形4

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

数字三角形必须经过某一个点，使之走的路程和最大

输入格式

第1行n，表示n行 <=25

第2到n+1行为每个的权值

第n+2行为两个数x,y表示必须经过的点

输出格式

最大值

测试样例1

输入

2

1

1 1

1 1

输出

2

备注

各个测试点1s

同前一道题的处理方式，不过必过的点变成了a[x][y]

1 #include
              
                2 #include
               
                 3 #include
                
                  4 #include
                 
                   5 using namespace std; 6 int a[30][30],n,ans=0,x,y; 7 int Max(int x,int y) 8 { 9     if(x>y)return x;10     else return y;11 }12 int main()13 {14     memset(a,0,sizeof(a));15     scanf("%d",&n);16     for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)scanf("%d",&a[i][j]);17     scanf("%d%d",&x,&y);18     a[x][y]+=99999;19     for(int i=n-1;i>=0;i--)20     {21         for(int j=1;j<=i;j++)22         {23             a[i][j]+=Max(a[i+1][j],a[i+1][j+1]);24         }25     }26     cout<
                  
                   <