首页 > 代码库 > Codeforces 417D Cunning Gena(状态压缩dp)
Codeforces 417D Cunning Gena(状态压缩dp)
题目链接:Codeforces 417D Cunning Gena
题目大意:n个小伙伴。m道题目,每一个监视器b花费,给出n个小伙伴的佣金,所须要的监视器数,以及能够完毕的题目序号。
注意,这里仅仅要你拥有的监视器数量大于小伙伴须要的监视器数量就可以。
求最少花费多少金额能够解决全部问题。
解题思路:dp[i],i为一个二进制数。表示完毕这些题目的最小代价,可是这里要注意,由于有个监视器的数量。普通情况下要开一个二维的状态。可是2^20次方有一百万,再多一维的数组会超内存,所以我的做法是将每一个小伙伴依照监视器的数量从小到达排序,慢慢向上加。
#include <cstdio> #include <cstring> #include <set> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int N = (1<<20)+5; const int M = 105; const ll INF = 0x3f3f3f3f3f3f3f3f; struct state { int s; ll k, val; }p[M]; int n, m; ll b, dp[N]; bool cmp (const state& a, const state& b) { return a.k < b.k; } void init () { memset(dp, -1, sizeof(dp)); scanf("%d%d", &n, &m); cin >> b; int t, a; for (int i = 0; i < n; i++) { cin >> p[i].val >> p[i].k >> t; p[i].s = 0; for (int j = 0; j < t; j++) { scanf("%d", &a); p[i].s |= (1<<(a-1)); } } sort(p, p + n, cmp); } ll solve () { dp[0] = 0; int t = (1<<m)-1; ll ans = INF; for (int i = 0; i < n; i++) { for (int j = 0; j <= t; j++) { if (dp[j] == -1) continue; int u = p[i].s | j; if (dp[u] == -1) dp[u] = p[i].val + dp[j]; else dp[u] = min(dp[u], p[i].val + dp[j]); } if (dp[t] != -1) ans = min(ans, dp[t] + p[i].k * b); } return ans == INF ? -1 : ans; } int main () { init (); cout << solve() << endl; return 0; }
Codeforces 417D Cunning Gena(状态压缩dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。