专栏文章

题解：P10973 Coins

cchase_the_light
P10973题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzu4xh
此快照首次捕获于
2025/12/01 18:15
3 个月前
此快照最后确认于
2025/12/01 18:15
3 个月前
查看原文
比较模板的一道题。
遇到这样的题目，首先可以想到拆分，但是显然地，直接把每个物品拆分成 CiC_i 个会超时，所以考虑优化。可以发现，当我们写出所有总和不超过 CiC_i 且可以表示为 2k2^k 的形式的数，并且再加上一个值为 CiC_i 减去这些数的和的数，用这些数互相加就可以表示出 [1,Ci][1,C_i] 区间内的所有数。于是我们就可以表示出每个物品购买 [1,Ci][1,C_i] 个的所有情况。
于是可以获得转移方程。令 dpjdp_j 表示是否可以用当前硬币凑出价值 jj，则当我遇到一个物品时，对于每个 jj，只要减去这个物品后我能够达成，这个 jj 我就一定也可以获得。即 dpj=dpj∨dpj−vidp_j = dp_j \lor dp_{j-v_i}。
代码就很好写了。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
using ll=long long;
bool dp[N];
int n,m,a[N],v[N],cnt,ans;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	while(1){
		cin>>n>>m;
		if(!(n||m)) break;
		for(int i=1;i<=n;i++) cin>>a[i];
		dp[0]=1;cnt=0;
		for(int i=1;i<=m;i++) dp[i]=0;
		for(int i=1,c;i<=n;i++){
			cin>>c;
			for(int j=1;j<=c;c-=j,j<<=1){
				v[++cnt]=j*a[i];
			}
			if(c) v[++cnt]=a[i]*c;
		}
		for(int i=1;i<=cnt;i++){
			for(int j=m;j>=v[i];j--){
				dp[j]|=dp[j-v[i]];
			}
		}
		ans=0;
		for(int i=1;i<=m;i++) ans+=dp[i];
		cout<<ans<<'\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...