F - Cards and Joy

思路:比较容易想到dp,直接dp感觉有点难,我们发现对于每一种数字要处理的情况都相同就是有 i 张牌 要给 j 个人分,

那么我们定义dp[ i ][ j ]表示 i 张牌给 j 个人分最大的价值可以得到dp方程如下:

dp[ i ][ j ] = max(dp[ i - u ][ j - 1 ] + f[ u ] )   u <= k

暴力转移就好了。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int> using namespace std; const int N = + ;
const int M = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +; LL dp[N][];
int n, k, a[N], f[N], h[N];
int cnt[M], num[M];
int main() { scanf("%d%d", &n, &k);
for(int i = ; i <= k * n; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++;
} for(int i = ; i <= n; i++) {
scanf("%d", &f[i]);
num[f[i]]++;
} for(int i = ; i <= k; i++) {
scanf("%d", &h[i]);
} for(int i = ; i <= n * k; i++) {
dp[i][] = h[min(k, i)];
for(int j = ; j <= n; j++) {
for(int u = ; i - u >= && u <= k; u++) {
dp[i][j] = max(dp[i][j], dp[i - u][j - ] + h[u]);
}
}
} LL ans = ;
for(int i = ; i <= 1e5; i++) {
if(num[i]) {
ans += dp[cnt[i]][num[i]];
}
} printf("%lld\n", ans);
return ;
}
/*
*/

最新文章

  1. 转: 如何高效利用GitHub
  2. Heatmap.js v2.0 – 最强大的 Web 动态热图
  3. 页面无法访问 css文件加载问题
  4. BZOJ一天提交 51纪念(二)
  5. php常用系统函数
  6. LNMP搭建(CentOS 6.3+Nginx 1.2.0+PHP 5.3.15(fpm)+ MySQL 5.5.35)
  7. js中apply和call的用法 以及apply的妙用 (来自网络)
  8. Windows系统版本号判定那些事儿
  9. 翻译 Asp.Net Core 2.2.0-preview1已经发布
  10. 50.Linux-分析ifconfig到内核的调用过程,实现内核启机自动设MAC地址(原)
  11. 整理Xen理论知识
  12. fibonacci数列-斐波那契数列-python编程
  13. three.js 3d三维网页代码加密的实现方法
  14. redis缓存服务器集群搭建
  15. Spark学习笔记-GraphX-1
  16. keras backend的修改
  17. IntelliJ IDEA 2017版 spring-boot 2.0.5 邮件发送简单实例 (三)
  18. python xml childNodes,childNodes[1].childNodes[0].data例子
  19. SCP报错:WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!
  20. 程序媛计划——mysql修改表结构

热门文章

  1. Ambari和ClouderaManager主要不同对比
  2. 平衡树【Treap】
  3. (转)使用Excel批量给数据添加单引号和逗号
  4. MongoDB 分页
  5. 去掉input获取focus时的边框
  6. 142.Linked List Cycle II---双指针
  7. 62.Unique Paths---dp
  8. sicily 1240. Faulty Odometer
  9. 剑指offer算法题
  10. [How to] HBase的bulkload使用方法