首页 > 代码库 > vijos P1426兴奋剂检查 多维费用背包问题的hash
vijos P1426兴奋剂检查 多维费用背包问题的hash
https://vijos.org/p/1426
这是个好题，容易想到用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 = 200 + 20; int dp[5000000 + 20]; int limit[maxn]; int w[maxn][10]; int val[maxn]; int togive; const int seed = 131; typedef unsigned long long int ULL; ULL powseed[10]; int first[100003 + 2]; ULL Edge[5000000 + 20]; int tonext[5000000 + 20]; int id[5000000 + 20]; int num; int toadd(ULL val) { int u = val % 100003; 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[1] + b * powseed[2] + c * powseed[3] + d * powseed[4] + e * powseed[5]; return toadd(val); } //适用于正负整数 template <class T> inline bool fast_in(T &ret) { char c; int sgn; if(c = getchar(), c == EOF) return 0; //EOF while(c != ‘-‘ && (c < ‘0‘ || c > ‘9‘)) c = getchar(); sgn = (c == ‘-‘) ? -1 : 1; ret = (c == ‘-‘) ? 0 : (c - ‘0‘); while(c = getchar(), c >= ‘0‘ && c <= ‘9‘) ret = ret * 10 + (c - ‘0‘); ret *= sgn; return 1; } void work() { int n, m; // cin >> n >> m; // scanf("%d%d", &n, &m); fast_in(n); fast_in(m); for (int i = 1; i <= m; ++i) { // cin >> limit[i]; // scanf("%d", &limit[i]); fast_in(limit[i]); } for (int i = 1; i <= n; ++i) { // cin >> val[i]; // scanf("%d", &val[i]); fast_in(val[i]); for (int j = 1; 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 = 0; for (int i = 1; i <= n; ++i) { for (int a1 = limit[1]; a1 >= w[i][1]; --a1) { for (int a2 = limit[2]; a2 >= w[i][2]; --a2) { for (int a3 = limit[3]; a3 >= w[i][3]; --a3) { for (int a4 = limit[4]; a4 >= w[i][4]; --a4) { for (int a5 = limit[5]; a5 >= w[i][5]; --a5) { int now = tohash(a1, a2, a3, a4, a5); int pre = tohash(a1 - w[i][1], a2 - w[i][2], a3 - w[i][3], a4 - w[i][4], a5 - w[i][5]); 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[0] = 1; for (int i = 1; i <= 5; ++i) { powseed[i] = powseed[i - 1] * seed; } work(); return 0; }
题解的那个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 = 200 + 20; int dp[5000000 + 20]; int limit[maxn]; int w[maxn][10]; int val[maxn]; int tohash(int a, int b, int c, int d, int e) { return (a * (limit[2] + 1) * (limit[3] + 1) * (limit[4] + 1) * (limit[5] + 1) + b * (limit[3] + 1) * (limit[4] + 1) * (limit[5] + 1) + c * (limit[4] + 1) * (limit[5] + 1) + d * (limit[5] + 1) + e); } //适用于正负整数 template <class T> inline bool fast_in(T &ret) { char c; int sgn; if(c = getchar(), c == EOF) return 0; //EOF while(c != ‘-‘ && (c < ‘0‘ || c > ‘9‘)) c = getchar(); sgn = (c == ‘-‘) ? -1 : 1; ret = (c == ‘-‘) ? 0 : (c - ‘0‘); while(c = getchar(), c >= ‘0‘ && c <= ‘9‘) ret = ret * 10 + (c - ‘0‘); ret *= sgn; return 1; } void work() { int n, m; // cin >> n >> m; // scanf("%d%d", &n, &m); fast_in(n); fast_in(m); for (int i = 1; i <= m; ++i) { // cin >> limit[i]; // scanf("%d", &limit[i]); fast_in(limit[i]); } for (int i = 1; i <= n; ++i) { // cin >> val[i]; // scanf("%d", &val[i]); fast_in(val[i]); for (int j = 1; 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 = 0; for (int i = 1; i <= n; ++i) { for (int a1 = limit[1]; a1 >= w[i][1]; --a1) { for (int a2 = limit[2]; a2 >= w[i][2]; --a2) { for (int a3 = limit[3]; a3 >= w[i][3]; --a3) { for (int a4 = limit[4]; a4 >= w[i][4]; --a4) { for (int a5 = limit[5]; a5 >= w[i][5]; --a5) { int now = tohash(a1, a2, a3, a4, a5); int pre = tohash(a1 - w[i][1], a2 - w[i][2], a3 - w[i][3], a4 - w[i][4], a5 - w[i][5]); 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 0; }
感觉我的hash才是正确的打开方式
vijos P1426兴奋剂检查 多维费用背包问题的hash
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。