当前位置 : 主页 > 网页制作 > HTTP/TCP >

【题解】luogu P5020 货币系统

来源:互联网 收集:自由互联 发布时间:2021-06-16
题目链接 https://www.luogu.org/problem/P5020 玄学题目。。。。可以用筛表,动规,搜索做 筛表 从小到大枚举,筛掉可以表示出来的数,剩下的数就是必须要选的(也就是答案)。 #includebit

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

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

 

筛表

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

#include<bits/stdc++.h> 
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<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
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],需要再加一层循环,极大的增加复杂度。

网友评论