题目描述
约翰有 N 头奶牛，组成了一直队伍参加全能比赛。比赛一共有 N 项，每头奶牛必须参加一项比
赛，每项比赛也必须有一头奶牛参加。任何一头奶牛可以胜任任何一项比赛，但得分不一样。如果第
i 头奶牛参加第 j 项比赛，在比赛结束的时候，可以为团体总分增加 S i,j 。
比赛是按照顺序依次进行的。除了上述获得分数的方法之外，还有 B 种奖励分。获得奖励的方法
是在前几项比赛里获得足够的分数。具体来说，第 i 项奖励会在第 K i 项比赛结束的时候检查，如果
当时的总分大于或等于 P i ，奶牛们就可以立即获得额外的 A i 分。如果有多项奖励在同一时刻检查，
奶牛可以*安排检查和加分的顺序。请问约翰应该如何安排奶牛参加比赛，才能让它们获得最高的
分数?
输入
• 第一行：两个整数 N 和 B，1 ≤ N ≤ 20, 1 ≤ B ≤ 20
• 第二行到第 B + 1 行：第 i + 1 行有三个整数 K i ，P i 和 A i ，1 ≤ K i ≤ N, 1 ≤ P i ≤ 40000,
1 ≤ A i ≤ 1000
• 第 B + 2 行到第 B + N + 1 行：第 i + B + 1 行有 N 个整数，代表 S i,1 到 S i,N ，对每个
1 ≤ j ≤ N, 1 ≤ S i,j ≤ 1000
输出
• 单个整数：表示奶牛们可以获得的最大得分
样例输入
3 1 2 7 6 5 1 7 2 2 4 4 2 1
样例输出
17
提示
第一项比赛由第一头奶牛参加，第二项比赛
由第三头奶牛参加，第三项比赛由第二头奶牛参加
题解：
n<=20 ->状压DP
然后定义F[i]表示i状态的奶牛，设now为i中1的数量，参加前now场比赛的最大得分
至于额外分这个东西，我把与比赛a有关的额外分都存在一个vector里 然后贪心 按pi从小到大排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=;
struct node{
int p,add;
};
vector<node>q[N+];
int s[N+][N+],F[<<N];
bool cmp(const node &p,const node &q){return p.p<q.p;}
int getday(int x)
{
int cnt=;
while(x)
{
cnt++;
x-=(x&(-x));
}
return cnt;
}
int main()
{
int n,m,x,y,z;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
q[x].push_back((node){y,z});
}
for(int i=;i<=n;i++)sort(q[i].begin(),q[i].end(),cmp);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&s[i][j]);
int mk=(<<n)-,now,tmp;
for(int i=;i<mk;i++)
{
now=getday(i);
for(int j=;j<=n;j++)
{
if((<<(j-))&i)continue;
tmp=F[i]+s[j][now+];
for(int k=,sz=q[now+].size();k<sz;k++)
if(tmp>=q[now+][k].p)tmp+=q[now+][k].add;
F[i|(<<(j-))]=max(F[i|(<<(j-))],tmp);
}
}
printf("%d",F[mk]);
return ;
}