poj-3176 Cow Bowling &&poj-1163 The Triangle && hihocoder #1037 : 数字三角形（基础dp）-白红宇

poj-3176 Cow Bowling &&poj-1163 The Triangle && hihocoder #1037 : 数字三角形（基础dp）

阅读量：5174 次

发布时间：2019-06-13

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

经典的数塔模型。

动态转移方程： dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+p[i][j];

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  15 #include 
                   
                    16 #pragma comment(linker, "/STACK:102400000,102400000")17 #define CL(arr, val) memset(arr, val, sizeof(arr))18 19 #define ll long long20 #define inf 0x7f7f7f7f21 #define lc l,m,rt<<122 #define rc m + 1,r,rt<<1|123 #define pi acos(-1.0)24 25 #define L(x) (x) << 126 #define R(x) (x) << 1 | 127 #define MID(l, r) (l + r) >> 128 #define Min(x, y) (x) < (y) ? (x) : (y)29 #define Max(x, y) (x) < (y) ? (y) : (x)30 #define E(x) (1 << (x))31 #define iabs(x) (x) < 0 ? -(x) : (x)32 #define OUT(x) printf("%I64d\n", x)33 #define lowbit(x) (x)&(-x)34 #define Read() freopen("a.txt", "r", stdin)35 #define Write() freopen("b.txt", "w", stdout);36 #define maxn 100000000037 #define N 50038 using namespace std;39 40 int dp[N][N];41 int main()42 {43 int n;44 scanf("%d",&n);45 for(int i=0;i
                    
                     =0;i--)48 for(int j=0;j<=i;j++)49 dp[i][j]=dp[i][j]+max(dp[i+1][j],dp[i+1][j+1]);50 printf("%d\n",dp[0][0]);51 return 0;52 }

只用一维数组。注意保证下一层的数由上一层推出，不受同一层的干扰。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  15 #include 
                   
                    16 #pragma comment(linker, "/STACK:102400000,102400000")17 #define CL(arr, val) memset(arr, val, sizeof(arr))18 19 #define ll long long20 #define inf 0x7f7f7f7f21 #define lc l,m,rt<<122 #define rc m + 1,r,rt<<1|123 #define pi acos(-1.0)24 25 #define L(x) (x) << 126 #define R(x) (x) << 1 | 127 #define MID(l, r) (l + r) >> 128 #define Min(x, y) (x) < (y) ? (x) : (y)29 #define Max(x, y) (x) < (y) ? (y) : (x)30 #define E(x) (1 << (x))31 #define iabs(x) (x) < 0 ? -(x) : (x)32 #define OUT(x) printf("%I64d\n", x)33 #define lowbit(x) (x)&(-x)34 #define Read() freopen("a.txt", "r", stdin)35 #define Write() freopen("b.txt", "w", stdout);36 #define maxn 100000000037 #define N 50038 using namespace std;39 40 int dp[N];41 int main()42 {43 //Read();44 int n,a,r=0;45 scanf("%d",&n);46 for(int i=1;i<=n;i++)47 {48 for(int j=i;j>=1;j--)49 {50 scanf("%d",&a);51 dp[j]=max(dp[j],dp[j-1])+a;52 r=max(r,dp[j]);53 //printf("%d ",dp[j]);54 }55 //printf("\n");56 }57 printf("%d\n",r);58 return 0;59 }