动态规划的数塔问题

1  #include
     
       2  #include
      
        3  using namespace std; 4  const int maxn = 1000; 5  int f[maxn][maxn],dp[maxn][maxn]; 6  int main(){ 7      int n; 8      scanf("%d",&n); 9      for(int i=1;i<=n;i++){10          for(int j=1;j<=i;j++){11              scanf("%d",&f[i][j]);12          }13      }14      for(int j=1;j<=n;j++){15          dp[n][j]=f[n][j];16      }17      for(int i=n-1;i>=1;i--){18          for(int j=1;j<=i;j++){19              dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];20          }21      } 22      printf("%d\n",dp[1][1]);23      return 0;24  }
      
     

 

最大连续子序列和

1  #include
     
       2  #include
      
        3  using namespace std; 4  const int maxn=10010; 5  int A[maxn],dp[maxn]; 6  int main(){ 7      int n; 8      scanf("%d",&n); 9      for(int i=0;i
       
        dp[k]){19              k=i;20          }21      }22      printf("%d\n",dp[k]);23      return 0;24  }
       
      
     

 最长不下降子序列（LIS）