个人如何在企业网站做实名认证/自助建站免费建站平台

题目

T(T<=20)组样例，每次n(n<=100)个数，第i个数ai(1<=ai<=25000)，表示货币金额，货币有无穷个，

问这其中最少保留多少个数，使得它们能表示出的面值和原来n个数能表示的面值相同

题解

一个trival的思维题，依次考虑每个数保不保留

第i小数没有用当且仅当不能被[1,i-1]的数表示出来

不要往小凯的疑惑上想，也不要想什么线性基

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105,M=25005;
int t,n,a[N],cnt;
bool dp[M];
int main(){scanf("%d",&t);while(t--){cnt=0;scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);}sort(a+1,a+n+1);memset(dp,0,sizeof dp);dp[0]=1;for(int i=1;i<n;++i){if(!dp[a[i]]){for(int j=a[i];j<M;j++){dp[j]|=dp[j-a[i]];			}}if(dp[a[i+1]]){cnt++;}}printf("%d\n",n-cnt);}return 0;
}