[USACO 2014 Gold] Cow Decathlon

作法：

如果不考慮 bonus 的話，就會變成基本的位元DP，設 dp[ i ] 代表已經派牛參加的運動集合為 i ，並且如果 i 的二進制中有 j 個 1 ，那麼就是前 j 隻牛參加 i 集合的運動所獲得的最大價值。而考慮 bonus 的話，我是先預處理出「在前 i 個運動中得到 j 分的話實際上可以獲得幾分」，並且在轉移的時候多考慮進來即可。而這個陣列的預處理方法是，對於每個 i ，把他對應的 bonus 們按照門檻由小到大排序，再一個一個去更新所求的陣列。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=20+1,maxc=40000+10 ;
 
struct P
{
    int val,add;
    bool operator < (const P &rhs) const
    {
        return val<rhs.val ;
    }
};
 
vector<P> v[maxn] ;
int earn[maxn][maxc] ;
void cal_earn()
{
    for(int i=1;i<maxn;i++)
    {
        for(int j=0;j<maxc;j++) earn[i][j]=j ;
        sort(v[i].begin(),v[i].end()) ;
        for(auto j : v[i])
            for(int k=maxc-1;earn[i][k]>=j.val;k--)
            earn[i][k]+=j.add ;
    }
}
 
int val[maxn][maxn] ;
int dp[1<<20] ;
vector<int> bit[maxn] ;
 
main()
{
    freopen("dec.in","r",stdin) ;
    freopen("dec.out","w",stdout) ;
    int n,B ; scanf("%d%d",&n,&B) ;
    while(B--)
    {
        int x,val,add ; scanf("%d%d%d",&x,&val,&add) ;
        v[x].push_back((P){val,add}) ;
    }
    for(int i=0;i<n;i++) for(int j=1;j<=n;j++)
        scanf("%d",&val[i][j]) ;
 
    cal_earn() ;
 
    for(int i=1;i<(1<<n);i++) bit[__builtin_popcount(i)].push_back(i) ;
 
    for(int i=1;i<=n;i++) for(auto j : bit[i])
        for(int k=0;k<n;k++) if(j&(1<<k))
            dp[j]=max(dp[j],earn[i][dp[j^(1<<k)]+val[k][i]]) ;
    printf("%d\n",dp[(1<<n)-1]) ;
}