算法标签 线性DP

题目简叙

思路

当前的状态由左上或者上方的两个点决定

代码

#include<iostream>using namespace std;int n;const int INF=1e9;
const int N=5e3+10;
int f[N][N],a[N][N];int main(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)cin>>a[i][j];//读入数据for(int i=0;i<=n;i++)    for(int j=0;j<=i+1;j++)f[i][j]=-INF;//初始化负无穷f[1][1]=a[1][1];//读入初始第一个数据for(int i=2;i<=n;i++)    for(int j=1;j<=i;j++)f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);//左上和上比较int res=-INF;for(int i=1;i<=n;i++)res=max(res,f[n][i]);//比较选择完之后的底部数据的最大值cout<<res;return 0;
}

AC记录