货币系统（简略）
2025-08-15 18:50:11
发布于：浙江
9阅读
0回复
0点赞
//复习题目的时候看了两遍此题正解代码，仍然做不出，遂急，书此篇。
链接描述
这道题目属于动态规划，但是思路有点难想。
在我初见这道题的时候，我使用了自己的聪明才智，尝试了出一个的代码。
事情是这样的，我认为这道题就是自己“内部消化”。
如果说有一个能被整除，那么这个就能被移除。
后来被测试点卡出。
因为第一个测试点的“19”是不能被其他三个数中的任意一个数整除的。
但是它可以有3和10凑出。
所以我就尝试，对于每一个，去判断其能否被另外两个数凑成。
遂40.
但是这其实是不对的。
因为也可能由三个数/更多的数凑成。
正解由DP写出。
但这个DP也不太一样。
首先是状态表示：
表示是否能有前面的数构成。
联想到“有个物品可以无限使用，能否装满一整个背包”的问题。
思路渐渐明了。
开始写代码吧。
底阿妈大概这样：
#include<bits/stdc++.h>
using namespace std;
int a[1005];
int dp[25005];
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
memset(dp,0,sizeof dp);
sort(a+1,a+1+n);
dp[0]=1;
int ans=0;
for(int i=1;i<=n;i++){
if(!dp[a[i]]){
ans++;
for(int j=a[i];j<=25005;j++){
dp[j]|=dp[j-a[i]];
}
}
}
cout<<ans<<endl;
}
int main(){
int t;
cin>>t;
while(t--)solve();
return 0;
}
这里空空如也
有帮助，赞一个