Codeforces 999F Cards and Joy

题面在这里

\(f_{i,j}\)表示\(i\)张卡片,分给\(j\)个人(所有卡片的编号和人的一样) \[ f_{i,j}=f_{i-k,j-1}+h[k] \] 然后统计一下答案就好了

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=505,maxk=15,maxs=5005;
int n,K,h[maxk],f[maxs][maxn],cnt[100005],num[100005];
#define up(x,y) (x=max(x,y))
int main(){
scanf("%d%d",&n,&K);
for (int i=1,x;i<=n*K;i++) scanf("%d",&x),cnt[x]++;
for (int i=1,x;i<=n;i++) scanf("%d",&x),num[x]++;
for (int i=1;i<=K;i++) scanf("%d",&h[i]);
for (int i=1;i<=n*K;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=i&&k<=K;k++)
up(f[i][j],f[i-k][j-1]+h[k]);
int ans=0;
for (int i=1;i<=100000;i++)
if (cnt[i]>0&&num[i]>0) ans+=f[cnt[i]][num[i]];
printf("%d",ans);
return 0;
}