codeforces 999F Cards and Joy

codeforces 999F Cards and Joy

​​ 题意好理解

我们分别求出对于每种喜爱的卡牌有j张给他分配i个人的最优代价

那么我们知道其他卡牌一定不会对他产生影响 那么我们只需要dp出这个值之后

贪心的选取即可 即设dp[i][j]表示i个人分j张卡牌时候的喜悦值最大 因为每个人的喜悦度h都是固定的 所以求解之后我们枚举每种卡牌 然后用他的张数和喜欢这种卡牌的人数贪心取dp值

其他因为不会对答案产生贡献所以无妨

#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;int n,k,c[N],f[N],dp[510][5010],ans,h[11];int main(){// freopen("f.in","r",stdin); n=read();k=read(); for (int i=1;i<=n*k;++i) ++c[read()]; for (int i=1;i<=n;++i) ++f[read()]; for (int i=1;i<=k;++i) h[i]=read(); for (int i=1;i<=n;++i) for (int j=1;j<=n*k;++j) for (int z=1;z<=min(j,k);++z) dp[i][j]=max(dp[i][j],dp[i-1][j-z]+h[z]); for (int i=1;i<=1e5;++i) if (f[i]) ans+=dp[f[i]][c[i]]; printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。