有體積分別為$1,2,...,8$的物品，給定各自的數(shù)量$cnt_1,cnt_2,...,cnt_8$和$W$，求這些物品能組成的最大且不超過(guò)$W$的體積和。 $cnt_i\leq 10^{16},\ W\leq 10^{18}$。

題目鏈接

---

\(Description\)
有體積分別為\(1,2,...,8\)的物品，給定各自的數(shù)量\(cnt_1,cnt_2,...,cnt_8\)和\(W\)，求這些物品能組成的最大且不超過(guò)\(W\)的體積和。
\(cnt_i\leq 10^{16},\ W\leq 10^{18}\)。

\(Solution\)
做法1：
考慮\(1,2,...,8\)能自己組成的最小的相同數(shù)為\(\mathbb{lcm}(1,2,...,8)=840\)，所以對(duì)每個(gè)數(shù)\(i\)，可以先組成盡可能多的\(A_i\)個(gè)\(840\)，剩下的\(i\)可以和其它剩下的數(shù)做背包，判斷能組成\(0\sim 839\)中的那些數(shù)以及還能組成多少個(gè)\(840\)。枚舉\(0\sim 839\)，顯然就能組成任意一個(gè)數(shù)了。
令\(f[i][j]\)表示當(dāng)前考慮了\(i\)個(gè)數(shù)，體積為\(j\)最多能組成的\(840\)個(gè)數(shù)。
這樣做每個(gè)數(shù)的實(shí)際數(shù)量為\(\frac{840}{i}\)，背包總體積\(840\)，復(fù)雜度\(O(840\times\sum\frac{840}{i})\)。

做法2：
同樣先考慮\(1,2,...,8\)能單獨(dú)組成的最小相同數(shù)為\(840\)。
記所有數(shù)的和為\(sum\)，只需考慮\(sum\gt W\)。
對(duì)于每個(gè)\(i\)用\(\frac{840}{i}\)個(gè)\(i\)做背包，可以求出能組成\(0\sim 839\)中的哪些數(shù)\(x\)，剩下的數(shù)可以用來(lái)組成任意\(t\)個(gè)\(840\)，只要滿足\(x+840t\leq sum\)，即\(t\leq\lfloor\frac{sum-x}{840}\rfloor\)。
同樣對(duì)于\(sum\)我們可以刪掉任意可行的\(x\)和任意\(t\)個(gè)\(840\)，只需滿足\(sum-x-840t\leq W\)，可得\(t\geq\lceil\frac{sum-x-W}{840}\rceil\)，即最小的\(t\)。所以背包后枚舉能組成的\(x\)即可。
背包可以用bitset優(yōu)化，復(fù)雜度\(O(\frac{8\times 840}{64})\)。

注意check一下邊界：\(sum-x<W\)時(shí)，因?yàn)?span id="w0obha2h00" class="math inline">\(sum>W\)，所以\(sum-x-W>-840\)，\(t_{min}=0\)，合法。
還有\(t\leq\lfloor\frac{sum-x}{840}\rfloor\)這個(gè)條件其實(shí)不用判。問(wèn)題只可能在于\(\lfloor\frac{sum-x}{840}\rfloor<\lceil\frac{sum-x-W}{840}\rceil\)，但若要\(ans\geq 0\)，則有\(ans=sum-x-840t\geq 0\)，即已有\(t\leq\lfloor\frac{sum-x}{840}\rfloor\)。

---

做法1：

//46ms	100KB
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back
typedef long long LL;
const int N=10,M=840;

LL cnt[N],f[N][M+5];

inline LL read()
{
	LL now=0,f=1; char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}

int main()
{
	LL W=read(),sum=0;
	for(int i=1; i<=8; ++i) cnt[i]=read(),sum+=cnt[i]*i;
	if(sum<=W) return printf("%lld\n",sum),0;

	memset(f,0xff,sizeof f);
	f[0][0]=0;
	for(int i=1; i<=8; ++i)
		for(int j=0; j<M; ++j)
		{
			LL val=f[i-1][j];
			if(val==-1) continue;
			for(int k=std::min(cnt[i],1ll*M/i); ~k; --k)
			{
				int t=(j+k*i)/M,v=(j+k*i)%M;
				f[i][v]=std::max(f[i][v],val+t+(cnt[i]-k)/(M/i));
			}
		}
	LL ans=0,val;
	for(int i=0; i<M; ++i)
		if(~(val=f[8][i]) && i<=W)
			ans=std::max(ans,i+std::min(val,(W-i)/M)*M);
	printf("%lld\n",ans);

	return 0;
}

做法2：

//31ms	0KB
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back
typedef long long LL;
const int N=10,M=840;

LL cnt[N];
std::bitset<M> f;

inline LL read()
{
	LL now=0,f=1; char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}

int main()
{
	LL W=read(),sum=0;
	for(int i=1; i<=8; ++i) cnt[i]=read(),sum+=cnt[i]*i;
	if(sum<=W) return printf("%lld\n",sum),0;

	f.reset(), f[0]=1;
	for(int i=1; i<=8; ++i)
		for(int t=std::min(cnt[i],1ll*M/i); t--; )
			f|=(f<<i);
	LL ans=0;
	for(int x=0; x<M; ++x)
		if(f[x])
		{
			LL t=(sum-x-W+M-1)/M;
//			if(t<=(sum-x)/M) ans=std::max(ans,sum-x-M*t);
			ans=std::max(ans,sum-x-M*t);
		}
	printf("%lld\n",ans);

	return 0;
}