Codeforces 417D

状压DP

学到一手,位操作时注意超出int用1LL进行位操作。

还有一个就是可以用排序从小到大进行降维。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
struct node
{
    long long m,num,can;//开始WA了后来丧心病狂全部改longlong
}node[105];
long long n,m,b;
bool vis[25];
long long dp[1LL<<20|1];
bool cmp(const struct node &a,const struct node &b)
{
    return a.num<b.num;
}
int main()
{
    cin>>n>>m>>b;
    memset(vis,false,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        int t,a;
        cin>>node[i].m>>node[i].num>>t;
        for(int j=0;j<t;j++)
        {
            cin>>a;
            vis[a]=true;
            node[i].can|=(1LL<<(a-1));
        }
    }
    int i;
    for(i=1;i<=m;i++)
    if(!vis[i])
    break;
    if(i!=m+1)
    {
        cout<<"-1"<<endl;//判-1的情况要注意
    }
    else
    {
        long long ans=(1LL<<60);
        for(int i=0;i<(1LL<<m);i++)
        dp[i]=(1LL<<60);
        sort(node,node+n,cmp);
        dp[0]=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<(1LL<<m);j++)
            {
                dp[j|node[i].can]=min(dp[j|node[i].can],dp[j]+node[i].m);
            }
            if(dp[(1LL<<m)-1]!=(1LL<<60))
            ans=min(ans,dp[(1LL<<m)-1]+node[i].num*b);//如果最大没更新说明没有优化,不用算上这个人,否则需要加上b*num
        }
        cout<<ans<<endl;
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券