vijos P1426兴奋剂检查多维费用背包问题的hash

这是个好题，容易想到用dp[i][v1][v2][v3][v4][v5]表示在前i个物品中，各种东西的容量是那个的时候，能产生的最大价值。

时间不会TLE,但是会MLE.所以就需要把那5维状态进行hash

其实就是对这个排列进行一个hash。

newState: v1, v2, v3, v4, v5这个排列。

oldState: v1 - w[1], v2 - w[2], v3 - w[3], v4 - w[4], v5 - w[5]

这个排列。

然后要进行hash。我写了一个hash。TLE 两组数据。

#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 <bitset>

const int maxn =  + ;

int dp[ + ];

int limit[maxn];

int w[maxn][];

int val[maxn];

int togive;

const int seed = ;

typedef unsigned long long int ULL;

ULL powseed[];

int first[ + ];

ULL Edge[ + ];

int tonext[ + ];

int id[ + ];

int num;

int toadd(ULL val) {

    int u = val % ;

    for (int i = first[u]; i; i = tonext[i]) {

        if (val == Edge[i]) return id[i];

    }

    ++num;

    tonext[num] = first[u];

    first[u] = num;

    Edge[num] = val;

    id[num] = ++togive;

    return togive;

}

int tohash(int a, int b, int c, int d, int e) {

    ULL val = a * powseed[] + b * powseed[] +

              c * powseed[] + d * powseed[] + e * powseed[];

    return toadd(val);

}

//适用于正负整数

template <class T>

inline bool fast_in(T &ret) {

    char c;

    int sgn;

    if(c = getchar(), c == EOF) return ; //EOF

    while(c != '-' && (c < '' || c > '')) c = getchar();

    sgn = (c == '-') ? - : ;

    ret = (c == '-') ?  : (c - '');

    while(c = getchar(), c >= '' && c <= '') ret = ret *  + (c - '');

    ret *= sgn;

    return ;

}

void work() {

    int n, m;

//    cin >> n >> m;

//    scanf("%d%d", &n, &m);

    fast_in(n);

    fast_in(m);

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

//        cin >> limit[i];

//        scanf("%d", &limit[i]);

        fast_in(limit[i]);

    }

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

//        cin >> val[i];

//        scanf("%d", &val[i]);

        fast_in(val[i]);

        for (int j = ; j <= m; ++j) {

//            cin >> w[i][j];

//            scanf("%d", &w[i][j]);

            fast_in(w[i][j]);

        }

    }

//    cout << tohash(1, 2, 3, 4, 5) << endl;

//    cout << tohash(1, 2, 4, 3, 5) << endl;

//    cout << tohash(1, 2, 3, 4, 5) << endl;

    int ans = ;

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

        for (int a1 = limit[]; a1 >= w[i][]; --a1) {

            for (int a2 = limit[]; a2 >= w[i][]; --a2) {

                for (int a3 = limit[]; a3 >= w[i][]; --a3) {

                    for (int a4 = limit[]; a4 >= w[i][]; --a4) {

                        for (int a5 = limit[]; a5 >= w[i][]; --a5) {

                            int now = tohash(a1, a2, a3, a4, a5);

                            int pre = tohash(a1 - w[i][], a2 - w[i][], a3 - w[i][], a4 - w[i][], a5 - w[i][]);

                            dp[now] = max(dp[now], dp[pre] + val[i]);

                            ans = max(ans, dp[now]);

                        }

                    }

                }

            }

        }

    }

    printf("%d\n", ans);

}

int main() {

#ifdef local

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

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

#endif

    powseed[] = ;

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

        powseed[i] = powseed[i - ] * seed;

    }

    work();

    return ;

}

题解的那个hash我真看不懂。不是看不懂，是不理解。

其实他的意思类似于a * 1000000 + b * 100000 + c * 1000 + e * 100 * d * 10

这样类似的。但是明显这个值太大了。他就乘上了limit[i]，这个我不能证明了，

好像又不会重复，数字又小。ORZ

#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 <bitset>

const int maxn =  + ;

int dp[ + ];

int limit[maxn];

int w[maxn][];

int val[maxn];

int tohash(int a, int b, int c, int d, int e) {

    return (a * (limit[] + ) * (limit[] + ) * (limit[] + ) * (limit[] + )

            + b * (limit[] + ) * (limit[] + ) * (limit[] + )

            + c * (limit[] + ) * (limit[] + ) + d * (limit[] + ) + e);

}

//适用于正负整数

template <class T>

inline bool fast_in(T &ret) {

    char c;

    int sgn;

    if(c = getchar(), c == EOF) return ; //EOF

    while(c != '-' && (c < '' || c > '')) c = getchar();

    sgn = (c == '-') ? - : ;

    ret = (c == '-') ?  : (c - '');

    while(c = getchar(), c >= '' && c <= '') ret = ret *  + (c - '');

    ret *= sgn;

    return ;

}

void work() {

    int n, m;

//    cin >> n >> m;

//    scanf("%d%d", &n, &m);

    fast_in(n);

    fast_in(m);

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

//        cin >> limit[i];

//        scanf("%d", &limit[i]);

        fast_in(limit[i]);

    }

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

//        cin >> val[i];

//        scanf("%d", &val[i]);

        fast_in(val[i]);

        for (int j = ; j <= m; ++j) {

//            cin >> w[i][j];

//            scanf("%d", &w[i][j]);

            fast_in(w[i][j]);

        }

    }

//    cout << tohash(1, 2, 3, 4, 5) << endl;

//    cout << tohash(1, 2, 4, 3, 5) << endl;

//    cout << tohash(1, 2, 3, 4, 5) << endl;

    int ans = ;

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

        for (int a1 = limit[]; a1 >= w[i][]; --a1) {

            for (int a2 = limit[]; a2 >= w[i][]; --a2) {

                for (int a3 = limit[]; a3 >= w[i][]; --a3) {

                    for (int a4 = limit[]; a4 >= w[i][]; --a4) {

                        for (int a5 = limit[]; a5 >= w[i][]; --a5) {

                            int now = tohash(a1, a2, a3, a4, a5);

                            int pre = tohash(a1 - w[i][], a2 - w[i][], a3 - w[i][], a4 - w[i][], a5 - w[i][]);

                            dp[now] = max(dp[now], dp[pre] + val[i]);

                            ans = max(ans, dp[now]);

                        }

                    }

                }

            }

        }

    }

    printf("%d\n", ans);

}

int main() {

#ifdef local

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

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

#endif

    work();

    return ;

}

感觉我的hash才是正确的打开方式

巴特西

vijos P1426兴奋剂检查多维费用背包问题的hash

最新文章

热门文章

巴特西

vijos P1426兴奋剂检查 多维费用背包问题的hash

最新文章

热门文章

vijos P1426兴奋剂检查多维费用背包问题的hash