P6775 [NOI2020] 制作菜品（dp，bitset）

传送门

---

解题思路

m：菜数 n：原料数

• 当 m=n-1 时：最小的跟最大的两两结合。

• 当 m>=n 时：最大的单独做，最后就变成了 m=n-1 的情况。

• 当 m=n-2 时：将每个物品减去k后做01可行性背包，可以使用 bitset 优化。

具体证明可以看这里：题解 P6775 【[NOI2020]制作菜品】

如何输出路径？

开n个bitset，第i个表示用前i个物品，然后倒序枚举物品，能转移就转移。

注意快读和关掉同步不能一块用，否则死循环会T掉？

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<bitset>
using namespace std;
template<class T>inline void read(T &x){
	cin>>x;
}
const int maxn=2500000;
bitset<maxn*2> dp[505];
int a[505],vis[505],n,m,k;
struct node{
	int v,id;
}d[505];
bool cmp1(node a,node b){
	return a.v<b.v;
}
void work1(int n){
	for(int i=1;i<n;i++){
		int minn=0,maxx=0;
		for(int j=1;j<=n;j++){
			if(d[a[j]].v==0) continue;
			if(minn==0||d[a[j]].v<d[minn].v) minn=a[j];
			if(maxx==0||d[a[j]].v>=d[maxx].v) maxx=a[j];
		}
		if(d[minn].v==k){
			cout<<d[minn].id<<' '<<k<<endl;
			d[minn].v=0;
		}else{
			cout<<d[minn].id<<' '<<d[minn].v<<' '<<d[maxx].id<<' '<<k-d[minn].v<<endl;
			d[maxx].v-=k-d[minn].v;
			d[minn].v=0;
		}
	}
}
bool DP(int n){
	dp[0][maxn]=1; 
	for(int i=1;i<=n;i++){
		if(d[i].v>=k) dp[i]=dp[i-1]|(dp[i-1]<<(d[i].v-k));
		else dp[i]=dp[i-1]|(dp[i-1]>>(-d[i].v+k));
	}
	if(!dp[n][maxn-k]) return 0;
	int now=maxn-k;
	for(int i=n;i>=1;i--){
		if(dp[i-1][now-(d[i].v-k)]){
			vis[i]=1;
			now-=d[i].v-k;
		}
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		memset(d,0,sizeof(d));
		memset(vis,0,sizeof(vis));
		read(n);read(m);read(k);
		for(int i=0;i<=n;i++) dp[i].reset();
		for(int i=1;i<=n;i++) read(d[i].v),d[i].id=i;
		sort(d+1,d+n+1,cmp1);
		if(m==n-1){
			for(int i=1;i<=n;i++) a[i]=i;
			work1(n);
		}else if(m>=n){
			int now=n;
			while(m!=n-1){
				if(d[now].v>k) d[now].v-=k;
				cout<<d[now].id<<' '<<k<<endl;
				if(d[now].v<=k) now--;
				m--;
			}
			sort(d+1,d+n+1,cmp1);
			for(int i=1;i<=n;i++) a[i]=i;
			work1(n);
		}else{
			if(!DP(n)){
				cout<<-1<<endl;
				continue;
			}
			int cnt=0;
			for(int i=1;i<=n;i++){
				if(vis[i]){
					a[++cnt]=i;
				}
			}
			work1(cnt);
			cnt=0;
			for(int i=1;i<=n;i++){
				if(!vis[i]){
					a[++cnt]=i;
				}
			}
			work1(cnt);
		}
	}
	return 0;
}

//NOI2020 Day2T1