codeforces 417D 状压DP

题意：多读英文题面有助于提高英语~~，要是你真忍不住就看代码下面吧。。

一开始觉得n*2^k是不是会GG啊，后来：cf怎么可能连1e8都不能过1e9都能过不是开玩笑的。
然后开始推，明显的设f[i][j]表示前i个状态为j，有：
$f[i][j|a[i].s]=min(f[i][j]+a[i].cost)$
有个问题就是他要求的那个显示器也要一定数量。然后一开始我打了个预处理，然后t了（不科学）。可能就算不T也是WA吧，反正就是强行处理基本上会挂。
事实上每一次枚举完状态j以后我们看看最大值是否更新(f[i][tot])，更新了就把当前枚举的那个朋友所需要的显示器费用加上去。注意这个地方不能随便加，要排个序，不然的话会加乱掉。
接下来你可以发现这明显空间会爆炸啊，于是我们滚动一下，然后你会发现TLE。
原因是每次滚动的时候赋值，常数GG，没想到cf还卡常。
那么我们就变成一维的，每次动态更新答案。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e5+5;
int n,m,b;
typedef long long ll;
const ll inf=1ll<<60;
ll f[1100000];
ll ans;
struct node
{
    int x,k,m,s;
}a[105];
bool cmp(node a,node b)
{
    return a.k<b.k;
}
bool vis[N];
int main()
{
    scanf("%d%d%d",&n,&m,&b);
    fo(i,1,n)
    {
        scanf("%d%d%d",&a[i].x,&a[i].k,&a[i].m);
        fo(j,1,a[i].m)
        {
            int x;
            scanf("%d",&x);
            a[i].s|=1<<(x-1);
            vis[x]=1;
        }
    }
    fo(i,1,m)
    {
        if (!vis[i])
        {
            printf("-1n");
            return 0;
        }
    }
    sort(a+1,a+1+n,cmp);
    int tot=(1<<m);
    ans=inf;
    fo(i,1,tot-1)f[i]=inf;
    fo(i,1,n)
    {
        fo(j,0,tot-1)
        {
            f[j|a[i].s]=min(f[j|a[i].s],f[j]+a[i].x);
        }
        if (f[tot-1]!=inf)
        ans=min(ans,f[tot-1]+1ll*a[i].k*b);
    }
    printf("%lldn",ans);
}

题意：n个小朋友，m个问题，每个显示器的花费b。
从第二行开始，有2*n行，第2*i行表示每个小朋友的花费，需要的显示器个数，和能解决的题目数量，2*i+1行表示第i个小朋友能解决的题目的编号。

最后

以上就是发嗲小懒虫为你收集整理的codeforces 417D 状压DP的全部内容，希望文章能够帮你解决codeforces 417D 状压DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。