[luogu] P1858 多人背包 01背包求前k优解

前言

传送门 :

思路

状态表示 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示从前 i i i个 物品里面选,体积是 j j j的第 k k k优解

状态计算 ： f [ j ] [ k ] = m a x ( d p [ j − 1 ] [ k ] , d p [ j − v ] [ k ] + v ) f[j][k] = max(dp[j-1][k],dp[j-v][k]+v) f[j][k]=max(dp[j−1][k],dp[j−v][k]+v)

f [ j ] [ k ] = m a x ( d p [ j ] [ 1... k ] ) f[j][k] =max(dp[j][1...k]) f[j][k]=max(dp[j][1...k])

因为 d p [ j − 1 ] [ k ] 和 d p [ j − v ] [ k ] dp[j-1][k]和dp[j-v][k] dp[j−1][k]和dp[j−v][k]是单调上升的因此

我们只需要维护两个队列,每次取出队头即可

Mycode

const int N  = 60, M  = 5e3+10 ,  N2 = 210;
int dp[M][N];

int v[N2],w[N2];
int ta[N],tb[N];

int k,V,n;

void solve(){
	cin>>k>>V>>n;
	for(int i=1;i>v[i]>>w[i];
	memset(dp,0xcf,sizeof dp);
	
	dp[0][1] = 0 ;
	
	
	for(int i=1;i=v[i] ;j -- ){
			for(int l = 1 ; l k ) break;
				if(p1 >k) dp[j][l] = tb[p2++];
				else if(p2 >k) dp[j][l]  = ta[p1++];
				else if(ta[p1] > tb[p2]) dp[j][l] = ta[p1++];
				else if(ta[p1]