首页 > 其他 > 详细

Codeforces Round #490(Div.3) F

时间:2018-06-25 00:50:12      阅读:72      评论:0      收藏:0      [点我收藏+]

标签:car   sum   scanf   fine   mes   names   efi   esp   IT   

题目大意

  • n个人,每个人有一个lucky number,每个人抽k张卡片。
  • 一个人如果抽到的卡片中有t个lucky number,这个人的价值为h[t]。
  • 求最大的价值和。

解题思路

  • 只需考虑带有lucky number的卡片,因为其他不是某个人的lucky number的卡片不会影响最后的价值。
  • 不同的lucky number是不会相互影响的。因为如果把某个人lucky number放到另一个lucky number不一样的人那里,只会降低最后的总价值。h是升序的。
  • 所以只需考虑有相同lucky number的人群中怎么分配带有他们的lucky number的卡片。而且不用在dp方程中加入lucky number,因为都是一样的,即与lucky number无关。
  • 令dp[x][y]为x个lucky number(记为q)相同的人,分配y张带有q的卡片的最大价值。则\(dp[x+1][y+i]=max\{dp[x][y]+h[i],0<=i<=k\}\),则最后的总价值为\(\mathit{ans} = \sum\limits_{i = 1}^{10^5}\mathit{dp}[f_i][c_i]\)

代码

#include <bits/stdc++.h>
#define REP(i,a,b) for (int i=(a); i<(b); i++)
using namespace std;

const int maxn = 6010;

int n, k;
int card[maxn], fav[510], joy[15];
int dp[520][maxn];
int f[100010], c[100010];

int main()
{
    scanf("%d%d", &n, &k);
    int tot = n * k;
    REP(i, 0, tot) {
        scanf("%d", &card[i]);
        c[card[i]]++;
    }
    REP(i, 0, n) {
        scanf("%d", &fav[i]);
        f[fav[i]]++;
    }
    REP(i, 1, k+1) scanf("%d", &joy[i]);
    REP(x, 0, n) REP(y, 0, tot) REP(i, 0, k+1) {
        dp[x+1][y+i] = max(dp[x+1][y+i], dp[x][y] + joy[i]);
    }
    int ans = 0;
    REP(i, 0, 100010) {
        if (f[i] != 0)
            ans += dp[f[i]][c[i]];
    }
    printf("%d\n", ans);
    return 0;
}

Codeforces Round #490(Div.3) F

标签:car   sum   scanf   fine   mes   names   efi   esp   IT   

原文:https://www.cnblogs.com/RFisher/p/9222178.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号