BZOJ 4971: [Lydsy1708月赛]记忆中的背包

神仙构造

分成x个1和一堆>=w-x的大物品 (x<=20 w>=50)

则拼成w的方案中有且仅有一个大物品

若最终序列中有x个1，有一个大物品为w-k，可以提供C(x,k)种方案

F[i][j]表示最终序列有i个1，方案数为j的最少大物品数

我也没算过为什么20就够了

但是20就是够了

模数这个神奇的东西没有用场

#include<cstdio>
using namespace std;
int C[25][25],F[25][20005],Pre[25][20005];
void Pre_C(){
	for (int i=0; i<=20; i++) C[i][0]=1;
	for (int i=0; i<=20; i++)
		for (int j=1; j<=i; j++)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
}
int main(){
	Pre_C();
	for (int i=0; i<=20; i++){
		for (int j=1; j<=20000; j++) F[i][j]=1e9;
		for (int j=0; j<=20000; j++)
			for (int k=0; k<=i; k++)
				if (j+C[i][k]<=20000 && F[i][j+C[i][k]]>F[i][j]+1){
					F[i][j+C[i][k]]=F[i][j]+1;
					Pre[i][j+C[i][k]]=k;
				}
	}
	int T;
	scanf("%d",&T);
	while (T--){
		int w,P,k;
		scanf("%d%d%d",&w,&P,&k);
		for (int i=1; i<=20; i++)
			if (F[i][k]+i<=40){
				printf("%d
",F[i][k]+i);
				for (int j=1; j<=i; j++) printf("%d ",1);
				while (k){
					int K=Pre[i][k];
					k-=C[i][K];
					printf("%d ",w-K);
				}
				printf("
");
				break;
			}
	}
	return 0;
}