首页 技术 正文
技术 2022年11月23日
0 收藏 908 点赞 3,048 浏览 2083 个字

背景

北京奥运会开幕了,这是中国人的骄傲和自豪,中国健儿在运动场上已经创造了一个又一个辉煌,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 1
6
7 3
8 5
3 1
6 2
4 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;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141367.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,075
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,505
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,317
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,311
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,912
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,099
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站