用最短路的形式写dp
众所周知,dp是一种特殊的最短路,它的状态转移可以看成具有拓扑序的图
所以将状态的起点加入,跑一遍最短路,把所有的节点都遍历到就好了(节点指的是 自己所定义的状态 $f[i]$,$f[i][j]$)
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
typedef pair<int,int> pii;
int angle[N][N];
int n;
int res[N][N];
int main(){
cin>>n;
memset(angle,-0x3f,sizeof angle);//初始化各个状态
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
scanf("%d",&angle[i][j]);
}
}
memset(res,-0x3f,sizeof res);
queue<pii>q;
q.push({1,1});
res[1][1]=angle[1][1];//起点
while(!q.empty()){
auto t=q.front();
q.pop();
if(t.first>n)//边界
continue;
if(res[t.first+1][t.second]<res[t.first][t.second]+angle[t.first+1][t.second])//遍历邻边
{ res[t.first+1][t.second]=res[t.first][t.second]+angle[t.first+1][t.second];
q.push({t.first+1,t.second});
}
if(res[t.first+1][t.second+1]<res[t.first][t.second]+angle[t.first+1][t.second+1])
{ res[t.first+1][t.second+1]=res[t.first][t.second]+angle[t.first+1][t.second+1];
q.push({t.first+1,t.second+1});
}
}
long long ans=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
if(ans<res[n][i])
ans=res[n][i];
}
cout<<ans;
}