2019 ICPC银川区域赛 Girls Band Party(分组背包)

2024-04-16 01:38

本文主要是介绍2019 ICPC银川区域赛 Girls Band Party(分组背包),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

You are currently playing a game called “Garupa”. In an event of the game, you are trying to get more event points. You have nn cards, each with its own name, color, and power. When you play the game, you can put five cards of different names into your deck. The base point of this event is the sum of the power of the cards in your deck. On top of that, the event publishes a color and five names as bonus attributes, which means that each time you have a card with a bonus color in the deck, you end up with a 20%20% increase in event point. And each time you have a card with a bonus name in the deck, you will eventually get 10%10% of the event point (bonus values are calculated by addition, and we round down when calculating the final event point). Please find the maximum event point you will eventually get.

Input
The first line is an integer T~(1 \leq T \leq 50T (1≤T≤50), which is the number of test cases.

For each set of input data, input a positive integer n~(5 \leq n \leq 100000)n (5≤n≤100000) in the first line to indicate the number of cards you have.

The next nn lines, the ii-th line input two strings name_iname
i

, color_icolor
i

and a positive integer power_i~(1 \leq power_i \leq 50000)power
i

(1≤power
i

≤50000) separated by spaces, indicating the name, color, and power of the ii-th card. The input data ensures that there are at least five cards with different names.

The next line input five strings representing the five bonus names. The input data guarantees that the bonus names are different.

The last line input a string representing a bonus color.

The input data ensures that all strings consist of only uppercase and lowercase letters and the max length of them is 1010, and the sum of nn in all sets of input data does not exceed 15000001500000.

Output
For each set of data, output only one line of a positive integer, indicating the maximum number of bonus points that you will eventually get.

样例输入复制
1
6
Saaya Power 45000
Kokoro Happy 45000
Kasumi Cool 45000
Rimi Power 45000
Aya Pure 45000
Aya Power 2000
Saaya Tae Kasumi Rimi Arisa
Power
样例输出复制
382500

题意:
每个物品有3个属性:名称 颜色 价值。
选中特定的名称会是总价值提升0.1倍,选中特定颜色会使总价值提升0.2倍
选5个不同名称物品使得价值和最大

思路:
状态很明显,就是选了多少个数字和提升了多少个0.1倍。将名称相同的物品放在一起,分组背包就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <map>
#include <vector>using namespace std;const int maxn = 1e5 + 7;map<string,int>mp1,mp2;
int dp[maxn][6][16];struct Node
{int val,num;string name,color;bool operator < (const Node&rhs)const{return name < rhs.name;}
}a[maxn];vector<Node>G[maxn];void init(int n)
{memset(dp,-1,sizeof(dp));mp1.clear();mp2.clear();for(int i = 1;i <= n;i++)G[i].clear();
}int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);init(n);for(int i = 1;i <= n;i++){cin >> a[i].name >> a[i].color >> a[i].val;}string tmp;for(int i = 1;i <= 5;i++){cin >> tmp;mp1[tmp] = 1;}cin >> tmp;mp2[tmp] = 2;sort(a + 1,a + 1 + n);int cnt = 0;for(int i = 1;i <= n;i++){if(a[i].name != a[i - 1].name){cnt++;}a[i].num = mp1[a[i].name] + mp2[a[i].color];G[cnt].push_back(a[i]);
//            cout << a[i].name << ' ' << a[i].color << ' ' << a[i].num << ' ' << a[i].val << endl;}dp[0][0][0] = 0;for(int i = 1;i <= cnt;i++){for(int k = 0;k <= 5;k++){for(int q = 0;q <= 15;q++){dp[i][k][q] = dp[i - 1][k][q];}}for(int j = 0;j < G[i].size();j++){int val = G[i][j].val,num = G[i][j].num;for(int k = 1;k <= 5;k++){for(int q = num;q <= 15;q++){if(dp[i - 1][k - 1][q - num] != -1){dp[i][k][q] = max(dp[i][k][q],dp[i - 1][k - 1][q - num] + val);}}}}}int ans = 0;for(int i = 0;i <= 5;i++){for(int j = 0;j <= 15;j++){ans = max(ans,dp[cnt][i][j] * (10 + j) / 10);}}printf("%d\n",ans);}return 0;
}

这篇关于2019 ICPC银川区域赛 Girls Band Party(分组背包)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907484

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

uva 10130 简单背包

题意: 背包和 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能