hack数据:`2 2 2 1 1 1`
你的输出:`Total=46`
正解:`Total=47`
你的做法漏掉了 $46$ 的情况,显然 $46$ 只能由 $1+2+2+3+3+5+10+20$ 得到。那么根据你的代码,导致这个问题的原因是:
在你第一次搜索到 `now=3` 时,`now` 是 `1+2` 得来的。想要得到上述 `46` 的情况,下一个搜索的应该是 `now=5` 。但是 `now=5` 已经在之前被 `1+1+3` 搜过了,`if(vis[now])` 这一句导致不能再往下搜了。于是就漏掉了 `46` 这一种情况。
by Untitled_unrevised @ 2021-11-10 01:15:03
这题也可以用01背包求方案数解决
```
#include<bits/stdc++.h>
using namespace std;
int w[100010],f[100010];
int main()
{
int a1,a2,a3,a4,a5,a6;
cin>>a1>>a2>>a3>>a4>>a5>>a6;
int cnt=0;
while(a1--)
{
w[++cnt]=1;
}
while(a2--)
{
w[++cnt]=2;
}
while(a3--)
{
w[++cnt]=3;
}
while(a4--)
{
w[++cnt]=5;
}
while(a5--)
{
w[++cnt]=10;
}
while(a6--)
{
w[++cnt]=20;
}
f[0]=1;
for(int i=1;i<=cnt;i++)
{
for(int j=1010;j>=0;j--)
{
if(j-w[i]>=0)
f[j]|=f[j-w[i]];
}
}
int ans=0;
for(int i=1;i<=1010;i++)
{
if(f[i])
ans++;
}
printf("Total=%d",ans);
return 0;
}
```
by mot1ve @ 2021-11-10 07:14:51
@[Untitled_unrevised](/user/76508) 恭喜您获得了年度最佳解疑奖!/jk
by AnYu的小Panda @ 2022-01-27 21:11:28