P4877 [USACO14FEB]Cow Decathlon G
题目描述
输入输出样例
输入 #1
3 1 2 7 6 5 1 7 2 2 4 4 2 1
输出 #1
17
分析
额......恩......嗯......咦......呃......这......
主要就是额外分难想(也不算难想),就是用一个结构体,运用贪心,先决要求(分数要求)给分数升序排序,先把能那的拿了,一些先觉要求高的(本来拿不到)也就有可能拿到。
Code
#include<bits/stdc++.h> using namespace std; int n,b; int f[1<<21];//二进制记录每头牛的状态,1表示这些牛已经打了比赛 int s[22][22]; struct node{ int k,p,a; }e[22]; bool cmp(node a,node b){//结构体成绩升序排序 return a.p < b.p; } int lowbit(int x){// return x & -x; } int count(int x){//计算有多少头牛 int cnt=0;//也就是计算该打第几场比赛了 for(int i=x;i;i-=lowbit(i)){ cnt++; } return cnt; } int main(){ scanf("%d%d",&n,&b); for(int i=1;i<=b;i++){ scanf("%d%d%d",&e[i].k,&e[i].p,&e[i].a); } sort(e+1,e+1+b,cmp); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&s[i][j]); } } int maxn = 1<<n; for(int i=0;i<maxn;i++){//枚举状态 int game = count(i);//计算game场数 for(int j=1;j<=n;j++){ if(i&(1<<(j-1))){//如果第j头牛打了比赛 f[i] = max(f[i],f[i^(1<<(j-1))]+s[j][game]);//max更新 } } for(int j=1;j<=b;j++){//枚举额外分 if(e[j].k==game&&f[i]>=e[j].p)f[i]+=e[j].a;//符合情况 } } printf("%d ",f[maxn-1]);//over return 0; }
OVER
完结撒花