dp做法100ptsWAhack数据求调
  • 板块P2409 Y的积木
  • 楼主wzc6666
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/25 19:57
  • 上次更新2024/7/25 20:50:30
查看原帖
dp做法100ptsWAhack数据求调
1000415
wzc6666楼主2024/7/25 19:57
#include<bits/stdc++.h>
using namespace std;
long long n,k,maxs,sum = 10;
long long m[1145];
long long w[1145][1145];
long long dp[114][114514];
bool cmp(int a,int b){
	return a>b;
}
int main(){
	cin>>n>>k;
	for(int i = 1;i<=n;i++){
		cin>>m[i];
		maxs = 0;
		for(int j = 1;j<=m[i];j++){
			cin>>w[i][j];
			maxs = max(maxs,w[i][j]);
		}
		sort(w[i]+1,w[i]+m[i]+1,cmp);
		sum+=maxs;
	}
	for(int i = 1;i<=n;i++){//n组物品 
		for(int j = sum;j>=1;j--){
			for(int k = 1;k<=m[i];k++){
				if(i==1&&j==w[i][k]){
					dp[i][j] += 1;
				}
				if(j>w[i][k]){
					dp[i][j]+=dp[i-1][j-w[i][k]];
				}
			}
		}
	}
	long long g = n;
	while(k>0){
		long long h;
		if(dp[n][g]>=k){
			h = k;
			k = 0;
		}else{
			k-=dp[n][g];
			h = dp[n][g];
		}
		for(int i = 1;i<=h;i++){
			cout<<g<<" ";
		}
		g++;
	}
	return 0;
}

2024/7/25 19:57
加载中...