题解 P1216 【[IOI1994][USACO1.5]数字三角形 Number Triangles】

Kenodi · 2019-08-27 15:35:47 · 题解

我没看到一个常规的dp解法，或者是我学艺不精，没读懂。 我这个用的是一个比较笨的方法。

#include<bits/stdc++.h>
using namespace std;
int a[1050][1050],dp[1050][1050];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    } 
    dp[1][1]=a[1][1];//第一个位置就直接读入进去 
    for(int i=2;i<=n;i++){
        dp[i][1]=a[i][1]+dp[i-1][1];//最左边的走法只能从上面一层走 
//      cout<<dp[i][1]<<" "<<a[i][1]<<" "<<dp[i-1][1]<<endl;
        for(int j=2;j<i;j++){
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
        }
        dp[i][i]=dp[i-1][i-1]+a[i][i];//最右边的走法同样只能从上面一层走

    }
    sort(dp[n]+1,dp[n]+n+1); //最后一层从小到大排序 
    cout<<dp[n][n]<<endl; //输出最大的 
//  for(int i=1;i<=n;i++){
//      for(int j=1;j<=i;j++){
//          cout<<dp[i][j]<<" ";
//      }   
//      cout<<endl;
//      
//  }
    return 0;
}