【状压dp】 Cunning Gena

Cunning Gena

---

分析：

很明显的一个状压dp
$f[i][j]$表示前i个人，组成解决问题的状态为j的最少花费
由于状态不好从前面转移（状态不唯一）
所以我们从前面往后面转移
第i个人的解题状态我们也用一个状压数组去表示(假设为s[i])
那么我们就有如下转移：
$f[i][j|s[i]]=min(f[i][j|s[i]],f[i-1][j]+x[i])$
由于当前只和前面一维有关，所以我们可以采用滚动数组。
采用滚动数组的时候需要注意，我们在当前这轮状态的时候很可能还保留着前一次状态的信息，所以我们每次重启一轮，都要重新赋值，放置前一轮的信息对这一轮产生影响。

但是这道题还有一个需要注意的点就是显示器的问题。
我们将人按照显示器从小到大排序，然后显示器的数量就有了单调性。
对于第i个人，当前的答案就是f数组的答案加上显示器的答案。

---

#include<bits/stdc++.h>
using namespace std;

#define ll long long
//#define inf 2e18+10
//const ll inf=2e18+10;
const ll N = (1<<20)+1,inf = 2e18+10;
ll f[2][N];
struct Node{
ll x,k;
int m,s;
}a[800];
int n,m;
ll b;

bool cmp(Node x,Node y){
return x.k < y.k;
}

inline int re(){
  int f = 1,x = 0;
  char ch = getchar();
  while(!isdigit(ch)){
if(ch == '-')f = -1;
  ch = getchar();
  }
  while(isdigit(ch)){
  x = (x << 1) + (x << 3) + (ch ^ 48);
  ch = getchar();
  }
  return x * f;
}

ll Min(ll x,ll y){
return x>y?y:x;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>b;
for (int i = 1; i <= n; i++){
cin>>a[i].x>>a[i].k>>a[i].m;
for (int j = 1,x; j <= a[i].m; j++)
  cin>>x,a[i].s|=(1<<(x-1));
}
for (int j = 1; j < (1<<m); j++) f[0][j] = inf;
sort(a+1,a+n+1,cmp);
ll ans = inf;
for (int i = 1; i <= n; i++){
for (int j = 0; j < (1<<m); j++) f[i&1][j] = inf;
for (int j = 0; j < (1<<m); j++){
    if (f[i+1&1][j] == inf) continue;
f[i&1][j|a[i].s] = Min(f[i&1][j|a[i].s],f[i+1&1][j]+a[i].x);
f[i&1][j] = min(f[i+1&1][j],f[i&1][j]);
}
ans = Min(ans,f[i&1][(1<<m)-1]+a[i].k*b);
}
printf("%lld\n",ans==inf?-1:ans);
return 0;
}

原文地址：https://blog.csdn.net/huang_ke_hai/article/details/140594250

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！