写在前面
这题其实不用排序。。。
$Idea$
$f[i]$表示$i$面值最多能被几张钱表示
若其不能被表示$f[i]=0xcf$ 能表示且只有它自己则$f[i]=1$
初始化$f[0]=0$
然后就是裸的背包
状态转移方程为$f[i]=\max(f[i],f[i-money[j]]+1)$
这里有两篇其他解法的
$Code$
int a[105],f[25005];
int T,n,ans;
int main(){
scanf("%d",&T);
while(T--){
memset(f,0xcf,sizeof f);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
ans=0; f[0]=0;
for(int i=1;i<=n;i++)
for(int j=a[i];j<=25001;j++)
f[j]=max(f[j],f[j-a[i]]+1);
for(int i=1;i<=n;i++)
if(f[a[i]]==1) ans++;
printf("%d\n",ans);
}
return 0;
}
$$ The \quad End $$
$$ \text{I’ve been painting every fence I know,Every color bleeds into the same;} $$
$$ \text{‘Cause before you go and walk away,Yeah you better know where you’re going.}\\ $$
$$ \text{-《Nevada》Vicetone/Cozi Zuehlsdorff} $$
代码是错的,踩
您是在逗我玩么?T_T
…