1354 选数字 DP背包 + 数学剪枝

时间：2023-12-13 21:51:20

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1354&judgeId=187448

其实这题和在若干个数字中，选取和为val，有多少种不同的选法是一样的。

只不过不能直接枚举背包容量，只能用map的iterate来枚举，这样来加速。

还有一个剪枝就是，所生成的数字要是val的约数，这些才加入去map那里，否则不加。

都是一些没用的状态。

还有这题不能用map的reverse_iterator，会蜜汁wa

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <hash_map>

using namespace __gnu_cxx;

const int MOD = ;

map<int, int>dp;

void init() {

    dp.clear();

}

void work() {

    init();

    int n, val;

    scanf("%d%d", &n, &val);

    dp[] = ;

    for (int i = ; i <= n; ++i) {

        int x;

        scanf("%d", &x);

////        if (val % x != 0) continue;

//        for (map<int, int> :: reverse_iterator it = dp.rbegin(); it != dp.rend(); ++it) {

//            if (val / it->first < x) continue;

//            if (val % (it->first * x) != 0) continue;

////            dp[it->first * x] = (dp[it->first * x] + (it->second)) % MOD;

//            dp[it->first * x] += it->second;

//            dp[it->first * x] %= MOD;

//        }

        map<int, int> :: iterator it = dp.end();

        it--;

        for(;; --it) {

            LL t = 1LL * it->first * x;

            if (t <= val && val % t == ) {

                dp[t] += it->second;

                dp[t] %= MOD;

            }

            if (it == dp.begin()) break;

        }

    }

    printf("%d\n", dp[val]);

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

相关文章