CoderForces999F-Cards and Joy
2 seconds
256 megabytes
standard input
standard output
There are nn players sitting at the card table. Each player has a favorite number. The favorite number of the jj-th player is fjfj.
There are k⋅nk⋅n cards on the table. Each card contains a single integer: the ii-th card contains number cici. Also, you are given a sequence h1,h2,…,hkh1,h2,…,hk. Its meaning will be explained below.
The players have to distribute all the cards in such a way that each of them will hold exactly kk cards. After all the cards are distributed, each player counts the number of cards he has that contains his favorite number. The joy level of a player equals htht if the player holds tt cards containing his favorite number. If a player gets no cards with his favorite number (i.e., t=0t=0), his joy level is 00.
Print the maximum possible total joy levels of the players after the cards are distributed. Note that the sequence h1,…,hkh1,…,hk is the same for all the players.
The first line of input contains two integers nn and kk (1≤n≤500,1≤k≤101≤n≤500,1≤k≤10) — the number of players and the number of cards each player will get.
The second line contains k⋅nk⋅n integers c1,c2,…,ck⋅nc1,c2,…,ck⋅n (1≤ci≤1051≤ci≤105) — the numbers written on the cards.
The third line contains nn integers f1,f2,…,fnf1,f2,…,fn (1≤fj≤1051≤fj≤105) — the favorite numbers of the players.
The fourth line contains kk integers h1,h2,…,hkh1,h2,…,hk (1≤ht≤1051≤ht≤105), where htht is the joy level of a player if he gets exactly tt cards with his favorite number written on them. It is guaranteed that the condition ht−1<htht−1<ht holds for each t∈[2..k]t∈[2..k].
Print one integer — the maximum possible total joy levels of the players among all possible card distributions.
4 3
1 3 2 8 5 5 8 2 2 8 5 2
1 2 2 5
2 6 7
21
3 3
9 9 9 9 9 9 9 9 9
1 2 3
1 2 3
0
In the first example, one possible optimal card distribution is the following:
- Player 11 gets cards with numbers [1,3,8][1,3,8];
- Player 22 gets cards with numbers [2,2,8][2,2,8];
- Player 33 gets cards with numbers [2,2,8][2,2,8];
- Player 44 gets cards with numbers [5,5,5][5,5,5].
Thus, the answer is 2+6+6+7=212+6+6+7=21.
In the second example, no player can get a card with his favorite number. Thus, the answer is 00.
题意:n∗kn∗k张卡片分给n个人,每人k张。第二行输入n∗kn∗k张卡片上面写的数字,第三行输入nn个人喜欢的数字,第四行输入k个数字,h[i]h[i]表示拿到ii张自己喜欢的卡片可以获得的快乐值。问所有人快乐值之和最大为多少?
题解:DP,dp[i][j],表示i个相同的数字给j个人(这j个人都喜欢这相同的数字);cnt[i]表示数字i的数量,num[j]表示喜欢j 的人数;
状态转换方程为:dp[i][j]=max(dp[i][j],dp[i-u][j-1]+w[u]);(1=<u<=k)
AC代码为:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,k,a[maxn],f[5005],w[15];
int cnt[maxn],num[maxn],dp[5005][521];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
memset(cnt,0,sizeof cnt);
memset(num,0,sizeof num);
cin>>n>>k;
for(int i=1;i<=n*k;i++) cin>>a[i],cnt[a[i]]++;
for(int i=1;i<=n;i++) cin>>f[i],num[f[i]]++;
for(int i=1;i<=k;i++) cin>>w[i];
for(int i=1;i<=n*k;i++)
{
dp[i][1]=w[min(i,k)];
for(int j=2;j<=n;j++)
{
for(int u=1;u<=min(i,k);u++)
dp[i][j]=max(dp[i][j],dp[i-u][j-1]+w[u]);
}
}
long long ans=0;
for(int i=1;i<maxn;i++) if(num[i]) ans+=dp[cnt[i]][num[i]];
cout<<ans<<endl;
return 0;
}
最新文章
- vm虚拟机安装雨林木风ghost镜像
- mysql 锁优化
- xshell 通过ssh连接 ubuntu15_x64
- Java 基础【11】@注解
- spring学习笔记---Jackson的使用和定制
- 【转】漫谈ANN(2):BP神经网络
- FPGA技术的一些基本概念(综合、BlackBox)(转)
- 采用WindowManager添加您自己的自定义视图
- 数据库及SQL----常用知识点总结
- R语言︱常用统计方法包+机器学习包(名称、简介)
- ThreadLocal是否会导致内存泄露
- identity server4 证书
- PHP引用(&;)练习
- iis 限制动态IP地址访问次数
- 快乐的Lambda表达式(二)
- DockerDesktop简单安装和使用
- SQL Server Collation解惑
- vue路由初始化路转
- 第二百七十一节,Tornado框架-CSRF防止跨站post请求伪造
- Spring编码过滤器:解决中文乱码