不行啊都开始卷了，补一下弱项
P5020 货币系统
个人认为题面写复杂了，真没啥必要。。。
很明显的背包问题。
设 \(dp_i\) 为面值为 \(i\) 的钱最多需要多少张货币来表示。
那么就直接跑背包就行了，表示不了的为 \(dp_i=-inf\)，能表示的且只有它自己能的为 \(dp_i=1\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4+5;
const int INF=0x7f7f7f7f;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int T,n;
int a[5005],dp[MAXN];//dp[i]表示面值为i的钱最多要多少张货币来表示
int main()
{
T=read();
while(T--)
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
memset(dp,-INF,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++)
for(int j=a[i];j<=25000;j++)
dp[j]=max(dp[j],dp[j-a[i]]+1);
int ans=0;
for(int i=1;i<=n;i++)
if(dp[a[i]]==1) ans++;
printf("%d\n",ans);
}
return 0;
}