F. Cards and Joy

题目大意：

给你n个人，每一个人恰好选k张牌。

第一行是 n 和 k

第二行有n*k个数，代表有n*k张牌，每张牌上的数字

第三行有n个数，代表第i个人喜欢的数字

第四行有k个数，代表有如果一个人可以拿到 i 张喜欢的牌，那么快乐值+h[i]

然后就是让你分配这些牌来找最大的欢乐值。

这个题目仔细想想就知道，因为这个h数组是递增的，所以我们就是要尽量把这个人喜欢的牌分配给她。

如果一种牌喜欢的人只有一个，那就把这个类型都给她，但是如果有很多人喜欢一样的牌，那就要合理分配使得x个人分配y张喜欢的牌使得欢乐值尽量大。

这个就是要dp了。

知道这个dp就很好d了。

dp[i][j] 表示i个人分配j张喜欢的牌，注意边界条件。

转移就是dp[i][j]=max(dp[i-1][j-x]+dp[1][x])

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <stack>

#include <bitset>

#include <vector>

#include <map>

#include <string>

#include <cstring>

#include <bitset>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn=1e5+;

typedef long long ll;

ll dp[][];

int c[maxn],f[maxn],h[maxn];

int vis[maxn],cnt[maxn];

pair<int,int>pii[maxn];

int main(){

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=;i<=n*k;i++) scanf("%d",&c[i]),vis[c[i]]++;

    for(int i=;i<=n;i++) scanf("%d",&f[i]),cnt[f[i]]++;

    for(int i=;i<=k;i++) scanf("%d",&h[i]);

    sort(f+,f++n);

    int len=unique(f+,f++n)-f-;

    int num=,peo=;

    for(int i=;i<=len;i++){

        pii[i]=make_pair(vis[f[i]],cnt[f[i]]);

        num=max(vis[f[i]],num);

        peo=max(cnt[f[i]],peo);

    }

    for(int i=;i<=min(num,k);i++) dp[][i]=h[i];

    for(int i=;i<=peo;i++){

        for(int j=;j<=num;j++){

            for(int x=;x<=min(j,k);x++){

                dp[i][j]=max(dp[i][j],dp[i-][j-x]+dp[][x]);

                // printf("dp[%d][%d]=%lld\n",i,j,dp[i][j]);

            }

        }

    }

    ll ans=;

    for(int i=;i<=len;i++){

        // printf("ww  %d %d\n",pii[i].second,pii[i].first);

        ans+=dp[pii[i].second][min(pii[i].first,pii[i].second*k)];

    }

    printf("%lld\n",ans);

    return ;

}

巴特西

F. Cards and Joy

最新文章

热门文章