首页 > 代码库 > vijos 1426 背包+hash
vijos 1426 背包+hash
背景
北京奥运会开幕了，这是中国人的骄傲和自豪，中国健儿在运动场上已经创造了一个又一个辉煌，super pig也不例外………………
描述
虽然兴奋剂是奥运会及其他重要比赛的禁药，是禁止服用的。但是运动员为了提高成绩难免要服用一些，super pig也不例外。为了不被尿检检查出来，这些药品就只能选一些不容易被发现的来服用。但是奥委会关于兴奋剂检查有很多个指标，只有尿检中各项数值均不高于规定指标才算成阴性（“你没服兴奋剂”），所以如何服用适量的药品使自己的水平达到最高是每个运动员困扰的问题。
现在有n个药品，每个药品如服用就必须全部用掉（否则会有副作用）。尿检检查共有m个项目，服用每个药品对于每个检查项目都会得到一定的效果值，这些效果值是累加的；服用每个药品当然还会给super pig一些水平提高值，这些效果也是累加的。现在super pig想把问题交给你来解决，因为吃药归吃药，训练才重要。
格式
输入格式
第一行有两个整数n (0<n<=200)和m (1<=m<=5)，分别表示药品数和需要检查的项目；
第二行m个整数 v1---vm，表示检查各项目的指标（即最高不能超过的值）；
第三行到第n+2行，分别是这n个药品的资料，每行m+1个数。每行第一个数表示服用该药品所得到的水平提高值，第二到第m+1个数分别表示服用这个药品每一项的效果值（分别对应第二行的指标类型）。
0<= k=1∏m Vk <=5000000
输出格式
一个整数，即super pig通过服这些药在不被检查出来的条件下所能得到的最高水平提高值
样例1
样例输入1[复制]
5 167 38 53 16 24 3
样例输出1[复制]
16
先吐个槽：我已经彻底走向DP只会背包的鶸鸡不归路了
题意：就是个01背包，只不过有五个背包。五个背包乘积小于等于 5000000
思路：直接开五维DP肯定不好，所以目标主要考虑如何压缩存储状态。我们可以粗略计算出某个维度所占用的大小，然后变成一维线性的（感觉空间上也没什么差别），总之非常神奇的没有RE。
/** @Date : 2016-11-29-18.54 * @Author : Lweleth (SoungEarlf@gmail.com) * @Link : https://github.com/ * @Version : */#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <utility>#include <vector>#include <map>#include <set>#include <string>#include <stack>#include <queue>//#include<bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+2000;int dp[5000010];int s[220][8];int main(){ int n, m; int a[8]; while(cin >> n >> m) { MMF(a); for(int i = 1; i <= m; i++) scanf("%d", a + i); for(int i = 1; i <= n; i++) { for(int j = 0; j <= m; j++) { scanf("%d", &s[i][j]); } } int ma = 0;d for(int i = 1; i <= n; i++) for(int j = a[1]; j >= 0; j--) for(int k = a[2]; k >= 0; k--) for(int l = a[3]; l >= 0; l--) for(int o = a[4]; o >= 0; o--) for(int p = a[5]; p >= 0; p--) { if(p >= s[i][5] && o >= s[i][4] && l >= s[i][3] && k >= s[i][2] && j >= s[i][1]) { int t = (((( j *(a[2] + 1) + k) *(a[3] + 1) + l) *(a[4] + 1) + o) *(a[5] + 1) + p); int x = (((( (j - s[i][1]) *(a[2] + 1) + (k - s[i][2])) *(a[3] + 1) + (l - s[i][3])) *(a[4] + 1) + (o - s[i][4])) *(a[5] + 1) + (p - s[i][5])); //cout << "~" << t << x << endl; dp[t] = max(dp[t], dp[x] + s[i][0]); ma = max(dp[t], ma); } } printf("%d\n", ma); } return 0;}vijos 1426 背包+hash