7

3   8

8   1   0

2   7   4   4

4   5   2   6   5

求自顶向下的最大和。

1 #include
     
       2 using namespace std; 3 const int maxn=606; 4  5 int main() 6 { 7     ios::sync_with_stdio(0); std::cin.tie(0); 8     int dp[maxn],a[maxn][maxn]; 9     int n;10     while( cin >> n){11         memset( dp, 0, sizeof dp);12         memset( a, 0, sizeof a);13         int mid=1;14         for(int i=1;i<=n;i++){15             for(int j=1;j<=mid;j++)16                 cin >> a[i][j];17             mid++;18         }19         mid=2;20         dp[1]=a[1][1];21         for(int i=2;i<=n;i++){22             for(int j=mid;j>0;j--){23                 dp[j]=max(a[i][j]+dp[j],a[i][j]+dp[j-1]);24             }25             mid++;26         }27         int ans=0;28         for(int i=1;i<=mid;i++)29             ans=max(ans,dp[i]);30 31         cout << ans <
     

还有一种更加简洁的写法，直接利用dp数组进行输出。

1 #include
     
       2 using namespace std; 3 const int maxn=606; 4  5 int main() 6 { 7     ios::sync_with_stdio(0); std::cin.tie(0); 8     int a[maxn][maxn]; 9     int n;10     while( cin >> n){11         int mid=1;12         for(int i=1;i<=n;i++)13             for(int j=1;j<=i;j++)14                 cin >> a[i][j];15 16         for(int i=n-1;i>=1;i--)17             for(int j=1;j<=i;j++)18                 a[i][j]=max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]);19 20         cout << a[1][1] <