Cunning Gena CodeForces

先将小伙伴按需要的监视器数量排序。然后ans[i][j]表示前i个小伙伴完成j集合内题目所需最少钱。那么按顺序枚举小伙伴，用ans[i-1][j]更新ans[i][j]和ans[i][j | 第i个小伙伴能完成题目的集合]（更新后一种时答案要加上第i个小伙伴的费用）。

由于小伙伴已经按监视器数量排序了，对于每个枚举出的小伙伴i，可以试着将其作为最后一个要求助的小伙伴，那么此时监视器上花的钱就是这个小伙伴所需监视器数量*每个的费用，求助小伙伴费用就是ans[i][所有题目的集合]，此时总费用就是这两者的总和。最终答案就是最小的枚举得到的总费用。

可以开滚动数组优化空间。

错误记录：45-47无效代码导致TLE

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 typedef long long LL;

 LL n,m1,b;

 struct A

 {

     LL x,k,v;

     bool operator<(const A& b) const

     {

         return k<b.k;

     }

 }aa[];

 LL ans[][];

 LL anss;

 int main()

 {

     LL i,j,k,t,tt,ii=;

     scanf("%I64d%I64d%I64d",&n,&m1,&b);

     for(i=;i<=n;i++)

     {

         scanf("%I64d%I64d%I64d",&aa[i].x,&aa[i].k,&tt);

         for(j=;j<=tt;j++)

         {

             scanf("%I64d",&t);

             //v[i].push_back(t);

             aa[i].v|=(<<(t-));

         }

     }

     sort(aa+,aa+n+);

     anss=0x3f3f3f3f3f3f3f3f;

     memset(ans,0x3f,sizeof(ans));

     ans[][]=;

     for(i=;i<n;i++)

     {

         ii^=;

         memset(ans[ii],0x3f,sizeof(ans[ii]));

         for(j=;j<(<<m1);j++)

         {

             ans[ii][j]=min(ans[ii][j],ans[ii^][j]);

             ans[ii][j|aa[i+].v]=min(ans[ii][j|aa[i+].v],ans[ii^][j]+aa[i+].x);

         }

         /*for(j=0;j<(1<<m1);j++)

             for(k=0;k<m1;k++)

                 ans[ii][j]=min(ans[ii][j],ans[ii][j|(1<<k)]);*/

         anss=min(anss,ans[ii][(<<m1)-]+b*aa[i+].k);

     }

     if(anss!=0x3f3f3f3f3f3f3f3f)

         printf("%I64d",anss);

     else

         printf("-1");

     return ;

 }

巴特西

Cunning Gena CodeForces - 417D

最新文章

热门文章