[NOIp2018]货币系统

筛法求解,一步步筛去可以表示的数,最后留下的不能被筛去的就是答案。

当然这也可以看作是一个完全背包。

在trans数组中:

  • 0:该面额不能被表示
  • 2:有该面额的货币
  • 1:该面额能被更小额的货币表示
#include <bits/stdc++.h>
using namespace std;

const int MAXT = 25001;
const int MAXN = 101;

int n;
int ans;
int trans[MAXT];
int coins[MAXN];

int main() {
    ios::sync_with_stdio(false);

    int t;

    cin >> t;

    while ( t-- ) {
        cin >> n;

        for ( int i = 1; i <= n; ++i ) {
            cin >> coins[i];
            trans[coins[i]] = 2;
        }

        sort(coins + 1, coins + 1 + n);

        for ( int i = 1; i <= coins[n]; ++i ) {
            if ( trans[i] ) {
                for ( int j = 1; j <= n; ++j )
                    if ( i + coins[j] <= coins[n] )
                        trans[i + coins[j]] = 1;
                    else
                        break;
            }
        }

        for ( int i = 1; i <= n; ++i )
            if ( trans[coins[i]] == 2)
                ++ans;

        cout << ans << endl;
                
        ans = 0;
        memset(trans, 0, sizeof(trans));
    }

    return 0;
}
Last modification:September 3rd, 2019 at 10:19 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment