1.如果1-a[1..n]中最大的数都能被表示出来，则任意非负整数均能被这个货币系统表示; (范围一定了)
2.等价的货币系统b中的币值一定属于a中的
3.如果已知货币系统中的币值能被当前已知币值表示，则这个币值可以舍弃
样例模拟： 4
3 19 10 6 首先1-19不能被表示的为: 1 2 4 5 7 8 11 14 17 证明1：
反证 ：如果存在大于19（对其他货币系统里的面值也适用）的数X不能被表示，那么X-19=Y也不能被表示，如果Y大于19，继续以上步骤，直到Y'<19不能被表示,与已知矛盾，证毕。
证明2：
反证：如果b中存在不属于a中的货币面值z。A.b中是最优解，因此b中的货币不会被存在于b中的其他货币表示出来。B.因为a和b等效，所以a不能表示的和b不能表示的一样（这点很重要）
那么如果这个z属于不能表示的币值，那么和B矛盾。如果这个z属于a能表示的币值（不包括a），那么 z就不能表示a中的某一个面值，矛盾。
综合1,2，可以得出3.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=105;
int t,n;
int a[N],f[25005];
int main()
{
cin>>t;
while(t--)
{
memset(a,0,sizeof a);
memset(f,0,sizeof f);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
f[0]=1;
sort(a+1,a+1+n);
int ans=n;
for(int i=1;i<=n;i++)
{
if(f[a[i]])
{
ans--;
continue;
}
for(int j=a[i];j<=a[n];j++)
f[j]|=f[j-a[i]];
}
cout<<ans<<endl;
}
return 0;
}
全部评论
(0) 回帖