rt,轮廓线dp的思路,先把数字都压到点上,再寻找轮廓线
以下代码40pts 不解啊(我菜,,,
总之非常非常非常需要帮助awa awa awa
#include<bits/stdc++.h>
using namespace std;
const int N=52;
int n,m,a[N][N],w[N][N],v[N][N];
int dp[N][N][N*N];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i+1;j++) scanf("%d",&a[i][j]);
}
//压轮廓线
for(int i=1;i<=n;i++) w[1][i]=1,v[1][i]=a[1][i];
for(int i=1;i<=n-1;i++) w[2][i]=1,v[2][i]=a[2][i];
for(int i=3;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
w[i][j]=w[i-2][j+1]+1,v[i][j]=v[i-2][j+1]+a[i][j];
}
}
//dp找最优轮廓线
int ans=0,sum=0;
for(int i=1;i<=n;i++){ //预处理第一列
sum+=w[i][1];
if(sum>m) break;
dp[i][1][sum]=dp[i-1][1][sum-w[i][1]]+v[i][1];
}
for(int j=2;j<=n;j++){
for(int i=1;i<=n-j+1;i++){
for(int k=m;k>=w[i][j];k--){
dp[i][j][k]=max(dp[i-1][j][k-w[i][j]],dp[i+1][j-1][k-w[i][j]])+v[i][j]; //从左上和左下转移状态
if(i==1) dp[i][j][k]=max(dp[i][j-1][k-1]+a[i][j],dp[i][j][k]); //第一行还可以直接从左边转移
if(k==m&&i==1){
ans=max(ans,dp[i][j][k]);
}
}
}
}
printf("%d",ans);
return 0;
}