假期培训A题
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int,int> PII;
typedef  pair<PII,int> pii;
const int N=510;
int dp[N][N],n,res,t;
/*
 问题：数字三角形
 闫氏dp分析法： 状态表示  f[i][j]:表示从底部到i，j点数字和的最大值；
   计算 f[i][j]=?
   什么呢？ dp从最后一个分界点去找
   i j 来自于=>  i-1,j or i-1,j-1;
   即将f[i][j]分割成两部分 first： 不变的 w[i][j] 变化的我们要取最大看f的含义即知f[i-1][j]or f[i-1][j-1]
   状态计算： f[i][j]=max(f[i-1)[j-1],f[i-1][j])+w[i][j];
 */
int main()
{  
    cin>>t;
    while(t--)
    {res=-10000010;
         cin>>n;
    memset(dp,-0x3f3f3f3f,sizeof dp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>dp[i][j];
        for(int i=2;i<=n;i++)
            for(int j=1;j<=i;j++)
                if(i==j)
                    dp[i][j]=dp[i-1][j-1]+dp[i][j];
                else
                dp[i][j]+=max(dp[i-1][j],dp[i-1][j-1]);
      for(int i=1;i<=n;i++)
    res=max(res,dp[n][i]);
            cout<<res<<endl;
    }
    return 0;
}
U题：
#include<bits/stdc++.h>
typedef  long long ll;
using namespace std;
typedef long long ll;
#define x first
#define y second
#define _for(i,a,b) for( int i=(a); i<=(b); ++i)
#define jfor(i,a,b) for(int i=x;i<=n;i+= lowbit(i))
typedef pair<int,int> PII;
typedef  pair<PII,int> pii;
typedef long long ll;
const int N=110,M=100010,inf=0x3f3f3f3f,mod=1e9+7;
int a[N][N],dp[N][N];
int t,n;
/*
 数字三角形：
 dp含义: 底部到i,j点的和
 属性max值
 计算dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
 */
int main()
{
  cin>>t;
  while(t--)
  {    memset(dp,0,sizeof dp);
      cin>>n;

      for(int i=1;i<=n;i++)
      for(int j=1;j<=i;j++)
          cin>>a[i][j];
      for(int i=n;i>0;i--)
          for(int j=1;j<=i;j++)
              dp[i][j]+= max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
          cout<<dp[1][1]<<endl;
  }
  return 0;
}