那一天的砖块WA了起来
查看原帖
那一天的砖块WA了起来
890346
Autumn_0930楼主2025/7/3 15:11

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;
} 

2025/7/3 15:11
加载中...