题解：P4877 [USACO14MAR] Sabotage G
题目大意
有 \(n\) 天，每天可以安排一个不同的奶牛挤奶。每头奶牛在第 \(i\) 天有特定的产量值，且在第 \(i\) 天结束时可能有多个奖励条件，求能获得的最大总产量。
题意分析
像这种没有思路的题目，先看一下 DP 可不可行，再观察到数据范围 \(n \le 20\)，不难想到状压，于是：
设 \(f_{i,mask}\) 表示前 \(i\) 天，已经挤过奶的奶牛集合为 \(mask\) 时的最大产量，接着考虑怎么转移。
状态转移
-
安排奶牛：对于第 \(i\) 天，从所有未挤奶的奶牛中选择一头，更新状态：
\[f_{i,mask+2^j} = \max(f_{i,mask+2^j}, f_{i-1,mask}+wis_{j,i}) \]其中 \(wis_{j,i}\) 表示奶牛 \(j\) 在第 \(i\) 天的产量。
-
奖励结算：在第 \(i\) 天结束时，根据当前产量 \(f_{i,mask}\) 结算奖励。
奖励条件按所需产量降序排序，依次判断并累加奖励值。
时间复杂度
状态数：\(O(n \cdot 2^n)\)。转移复杂度：\(O(n)\)，总复杂度：\(O(n \cdot 2^n)\)，还有一点小常数。在 \(n \le 20\) 时可接受。
CODE
#include<bits/stdc++.h>
#define wk(x) write(x),putchar(' ')
#define wh(x) write(x),putchar('\n')
#define N 21
#define M 1100005using namespace std;
int n,m,k,ans;
int wis[N][N],f[N][M];struct Q{int x,y;bool operator<(const Q&A)const{return A.x<x;}
};vector<Q> kis[N];void read(int &x){x=0;int ff=1;char ty;ty=getchar();while(!(ty>='0'&&ty<='9')){if(ty=='-') ff=-1;ty=getchar();}while(ty>='0'&&ty<='9')x=(x<<3)+(x<<1)+ty-'0',ty=getchar();x*=ff;return;
}void write(int x){if(x==0){putchar('0');return;}if(x<0){x=-x;putchar('-');}char asd[201];int ip=0;while(x) asd[++ip]=x%10+'0',x/=10;for(int i=ip;i>=1;i--) putchar(asd[i]);return;
}int Get(int x,int y=0){while(x){if(x&1) y++;x>>=1;}return y;
}signed main(){read(n),read(m);for(int i=1,x,y,z;i<=m;i++){read(x),read(y),read(z);kis[x].push_back((Q){y,z});}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){read(wis[i][j]);}}for(int i=1;i<=n;i++) sort(kis[i].begin(),kis[i].end());//按p排序肯定最优，这点需要注意！for(int i=1;i<=n;i++){for(int p=0;p<=(1<<n)-1;p++){if(Get(p)!=i-1) continue;//避免无效状态for(int j=1;j<=n;j++){if((p|(1<<(j-1)))==p) continue;//重复f[i][p|(1<<(j-1))]=max(f[i][p|(1<<(j-1))],f[i-1][p]+wis[j][i]);//转移ans=max(f[i][p|(1<<(j-1))],ans);//取最大值}}for(int p=0;p<=(1<<n)-1;p++){if(Get(p)!=i) continue;//避免无效状态，同上for(int j=0;j<(int)kis[i].size();j++){if(f[i][p]>=kis[i][j].x) f[i][p]+=kis[i][j].y,ans=max(f[i][p],ans);//计算奖励分}}}wh(ans);return 0;
}