2019银川icpc A 分组背包

题意：

有$n$张卡片，每张卡片有$name,color,power$属性，给出$5$个特殊的$name$，$1$个特殊的$color$。总得分定义为卡片的$power$之和乘$bonus$系数，初始是$bonus$为$1$，每张卡片满足$name$是特殊的时候$bonus+0.1$，$color$是特殊的时候$bonus+0.2$。需要从$n$张卡内选出$5$张，使得他们$name$两两互异，并且使得总得分最大

Solution：

明显是个分组背包，但如何定义状态？若我们像普通的分组背包，定义$f[i]$为已装$i$容量的物品的最大价值，实际上题目的价值是随前面的总价值变化而变化的，难以转移，并且似乎考虑不到所有的状态。造成这一现象的原因是$bonus$在变化，于是考虑将$bonus$加入状态，定义$f[i][j]$为装了容量为$i$的物品，此时$bonus=10\times j$的最大$power$和为多少，这样就能够考虑到所有状态了。显然我们首先需要对卡片按名字分组，于是不妨来一次排序，然后双指针找出同名的一段，枚举加入的卡片为$k$，有
$$dp[i][j]=max(dp[i][j],dp[i-1][j-val]+a[k].power);$$
答案就是$max(dp[5][i]+dp[5][i]\ast i/10)$。需要注意初始化时只有$dp[0][0]=0$，其他都置为负无穷，以保证转移的源头都是状态$(0,0)$

#ifndef stdjudge
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=1e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=998244353;

struct poker
{
	string name,color;
	int power;
	bool operator<(const poker& x) const {
		return name<x.name;
	}
}a[N];
unordered_map<string,bool>map1;
string color;

int n;
ll dp[6][16];

int getval(int x) {
	return map1.count(a[x].name)+2*(a[x].color==color);
}

int main()
{
	#ifdef stdjudge
		freopen("in.txt","r",stdin);
	#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t; cin>>t;
	while(t--)
	{
		cin>>n; map1.clear();
		for(int i=1;i<=n;i++) cin>>a[i].name>>a[i].color>>a[i].power;
		for(int i=1;i<=5;i++)
		{
			cin>>color;
			map1[color]=true;
		} 
		cin>>color;
		sort(a+1,a+1+n);
		for(int i=0;i<=5;i++)
			for(int j=0;j<=15;j++) dp[i][j]=-INF;
		int l=1,r=1; dp[0][0]=0;
		while(l<=n)
		{
			while(r+1<=n&&a[r+1].name==a[l].name) r++;
			for(int i=5;i>=1;i--)
			{
				for(int j=0;j<=15;j++)
				{
					for(int k=l;k<=r;k++)
					{
						int val=getval(k);
						if(j>=val) dp[i][j]=max(dp[i][j],dp[i-1][j-val]+a[k].power);
					}
				}
			}
			l=++r;
		}
		ll ans=-INF;
		for(int i=0;i<=15;i++) ans=max(ans,dp[5][i]+dp[5][i]*i/10);
		cout<<ans<<'\n';
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81