【Usaco2014 Feb】Cow Decathlon

に言及
FJにはN(1<=N<=20)頭の乳牛があり、番号は1~Nである.FJはN種類の異なる技能を提供して乳牛たちに学ぶことができて、すべての乳牛は1つの技能しか学ぶことができなくて、すべての技能はすべて乳牛が学ぶことがあります.第i頭乳牛は第j門技能を学び、FJが得た点数はS[i][j]、1<=S[i][j]<=1000である.他にもB(1<=B<=20)個の奨励があり、i番目の奨励のフォーマットは:Ki、Pi、Aiであり、学習前のKi門技能後の総得点(追加の奨励得点を含む)がPiより少なくなければ、FJは追加のAi点を得ることができるという意味である.FJはどのように乳牛学習技能を手配して、最後の総得点を最高にすることができるのか.
サンプル
Sample Input 3 1 2 7 6 5 1 7 2 2 4 4 2 1
Sample Output 17
OUTPUT DETAILS: Cow 1 will perform event 1, cow 3 will perform event 2, and cow 2 will perform event 3.
乳牛1学習スキル1、乳牛2学習スキル3、乳牛3学習スキル2.
ぶんせき
状圧DPは、牛1頭あたりの使用状況をバイナリ圧縮f[i]で表した状態がi(バイナリ)の場合、得られる最大点は奨励金を個の構造体で保存し、奨励金が得られるかどうかを判断するたびにいいし、吊り下げた関数は__builtin_popcountというので、自分で調べてコードを見てもいいでしょう.
コード#コード#

//Problem:【Usaco2014 Feb】Cow Decathlon
//weiqiang he
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=20+2;
int n,b,s[maxn][maxn],l[maxn],r[maxn];
int f[1<<maxn];
void readin(int &ret)    //     
{
    ret=0;
    char c;
    while((c=getchar()),(c>'9'||c<'0'));
    do{
        (ret*=10)+=c-'0';
    }
    while((c=getchar()),(c<='9'&&c>='0'));
}
struct node{
    int k,p,a;
}t[maxn];
bool cmp1(node a,node b){return a.k<b.k;}
bool cmp2(node a,node b){return a.p<b.p;}
int main()
{
    for(int i=0;i<maxn;i++)  l[i]=r[i]=-1;    //   l r 
    int i,j,k,p,a;
    readin(n);readin(b);
    for(i=0;i<b;i++)
    {
        readin(k);readin(p);readin(a);
        t[i].k=k;t[i].p=p;t[i].a=a;
    }
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
      {
        readin(a);
        s[i][j]=a;
      }
    sort(t,t+b,cmp1);
    for(i=0;i<b;i++)
    {
        j=i;
        while(i+1<=n&&t[i].k==t[i+1].k) i++;
        sort(t+j,t+i+1,cmp2);
        l[t[j].k]=j;
        r[t[j].k]=i;
    }
    int S=1<<n;
    for(i=1;i<S;i++)
    {
        k=__builtin_popcount(i);  //__builtin_popcount:             
        for(j=1;j<=n;j++)
        {
            if(i&1<<j-1)        //         
                f[i]=max(f[i],f[i-(1<<j-1)]+s[j][k]);
        }
        if(l[k]!=-1)
        {
            for(j=l[k];j<=r[k];j++)
              if(f[i]>=t[j].p)
                f[i]+=t[j].a;
              else 
                break;
        }
    }
    printf("%d
",f[S-1]);
    return 0;
}