题目链接 https://www.luogu.org/problem/P5020

玄学题目。。。。可以用筛表，动规，搜索做

 

筛表

从小到大枚举，筛掉可以表示出来的数，剩下的数就是必须要选的（也就是答案）。

#include
     
       using namespace std;int dp[25005], t, a[105], n, sum;int main(){    cin >> t;    while(t--)    {        memset(a, 0, sizeof(a));        memset(dp, 0, sizeof(dp));        sum = 0;        cin >> n;        for(int i = 1; i <= n; i++)        {            cin >> a[i];            dp[a[i]] = 2;        }            sort(a+1, a+1+n);        for(int i = 1; i <= a[n]; i++)        {            if(dp[i] > 0)            {                    for(int j = 1; j <= n; j++)                    if(i+a[j] <= a[n])                        dp[i+a[j]] = 1;                    else break;            }        }        for(int i = 1; i <= a[n]; i++)            if(dp[i] == 2) sum++;        cout << sum << endl;    }    return 0;}
     

 

动态规划

/*状态 m, dp[i]dp[i]代表面值为i的纸币最多有几种表示 注意这是个刚好装满的完全背包问题（注意初始化）dp[i] = max(dp[i], dp[i-a[i]]+1);*/#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int a[105], n, q[30000], t, ans;int main(){    cin >> t;   while(t--)   {           ans = 0;           memset(q,-63,sizeof q);        cin >> n;        for(int i = 1; i <= n; i++)            cin >> a[i];        q[0]=0;        for(int i = 1; i <= n ; i++)            for(int j = a[i]; j <= 25005; j++)                q[j] = max(q[j], q[j-a[i]]+1);        for(int i = 1; i <= n; i++)            if(q[a[i]] == 1) ans++;        cout << ans << endl;      }           return 0;}
        
       
      
     

启示：刚好装满问题中

1.将dp[i] 初始化为-inf ，dp[i] = max(dp[i], dp[i-a[i]]+1);

2.没有初始化dp[i],需要再加一层循环，极大的增加复杂度。

 

//记忆化搜索 #include
     
      using namespace std;int a[105], cnt, vis[25005], ans, t, x, n, f[25005];void dfs(int now, int sum, int x){    for(int i = x; i <= n; i++)    {        if(a[i]+now <= a[n] && !vis[now+a[i]])        {            vis[now+a[i]] = 1;            f[now+a[i]] = sum;            dfs(now+a[i], sum+1, i);        }    }    }int main(){    cin >> t;    while(t--)    {        ans = 0;        memset(a, 0, sizeof(a));        memset(f, 0, sizeof(f));        memset(vis, 0, sizeof(vis));        cin >> n;        for(int i = 1; i <= n; i++)            cin >> a[i];        sort(a+1, a+1+n);        dfs(0, 0, 1);        for(int i = 1; i <= n; i++)            if(f[a[i]] == 0) ans++;        cout << ans << endl;    }        return 0;}