NC20663 dp

这题数据还是有点水啊，，四重循环过了。看到有大佬做了优化不过暂时没研究。
关键步骤是想到我们按列划分子状态，每处理一个子三角后可以在它右边“贴上”一列技能点，贴上的边不能长于原三角右侧边长度+1，我们用dp[i][j][k]表示从左至右的第i列选了j个技能，总使用技能点数k情况下的最大收益，就可以写出状态转移式dp[i][j][k]=max(dp[i-1][j-1i-1][j(j+1)/2m])，复杂度n^3m。

#include<bits/stdc++.h>
using namespace std;

const int maxn=51;
const int maxm=1301;
int a[maxn][maxn];
int n,m;
int dp[maxn][maxn][maxm];

int main(){
    while(cin>>n>>m){
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                cin>>a[j][i];
                a[j][i]+=a[j][i-1];
            }
        }
        int ans=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            for(int j=0;j<=i;j++){
                for(int k=(j+1)*j/2;k<=m;k++){
                    for(int lst=max(0,j-1);lst<=i-1;lst++){
                        dp[i][j][k]=max(dp[i-1][lst][k-j]+a[i][j],dp[i][j][k]);
                    }
                }
                ans=max(ans,dp[i][j][m]);
            }
        }
        cout<<ans<<endl;
    }
}