正文 

当前位置： 首页 > java > java教程

bzoj3446[usaco2014feb]cowdecathlon*

YuanZiming YuanZiming     2022-08-13     673

关键词：

bzoj3446[Usaco2014 Feb]Cow Decathlon

题意：

FJ有n头奶牛。FJ提供n种不同的技能供奶牛们学习，每头奶牛只能学习一门技能，每门技能都要有奶牛学习。 第i头奶牛学习第j门技能，FJ得到的分数S[i][j]。此外还有b个奖励，第i个奖励的格式是： Pi 、Ki 、Ai，表示的意义是：如果学习完前Ki门技能后的总得分（包括额外的奖励得分）不少于Pi，那么FJ还会得到额外的Ai分。求通过安排奶牛学习技能，所能取得的最高总得分。n，b≤20。
题解：
状压dp。f[i][S]表示当前考虑第i个技能，奶牛是否学习技能的状态为S，则f[i][S]=max(f[i-1][S&((1<<n)-1-(1<<(l-1)))]+s[l][i])然而这样可能会T因为复杂度是O(n^2*2^n)，所以可以先预处理出所有S中1的个数，之后在转移时只有bit[S]==i时才能发生转移。
代码： 
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 30
 7 using namespace std;
 8 
 9 inline int read(){
10     char ch=getchar(); int f=1,x=0;
11     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}
12     while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();
13     return f*x;
14 }
15 int n,b,s[maxn][maxn],f[2][1500000],bit[1500000]; bool x,y;
16 struct nd{int p,a,n;}nds[maxn]; int g[maxn],tot;
17 int main(){
18     n=read(); b=read();
19     inc(i,1,b){int x=read(); nds[i].p=read(); nds[i].a=read(); nds[i].n=g[x]; g[x]=i;}
20     inc(i,1,n)inc(j,1,n)s[i][j]=read(); x=0; y=1;
21     inc(i,0,(1<<n)-1){bit[i]=0; inc(j,0,n-1)if(i&(1<<j))bit[i]++;}
22     inc(i,1,n){
23         inc(j,0,(1<<n)-1)if(bit[j]==i){
24             inc(l,1,n)if(j&(1<<(l-1)))f[y][j]=max(f[y][j],f[x][j&((1<<n)-1-(1<<(l-1)))]+s[l][i]);
25             for(int l=g[i];l;l=nds[l].n)if(f[y][j]>=nds[l].p)f[y][j]+=nds[l].a;
26         }
27         swap(x,y);
28     }
29     printf("%d",f[x][(1<<n)-1]); return 0;
30 }

 

20161116

[bzoj]1651:[usaco2006feb]stallreservations专用牛棚

1651:[Usaco2006Feb]StallReservations专用牛棚TimeLimit:10Sec  MemoryLimit:64MBSubmit:987  Solved:566[Submit][Status][Discuss]DescriptionOhthosepickyN(1<=N<=50,000)cows!Theyaresopi 查看详情

[bzoj1651][usaco2006feb]stallreservations专用牛棚

1651:[Usaco2006Feb]StallReservations专用牛棚TimeLimit:10Sec  MemoryLimit:64MBSubmit:990  Solved:568[Submit][Status][Discuss]DescriptionOhthosepickyN(1<=N<=50,000)cows!Theyaresopi 查看详情

bzoj3445:[usaco2014feb]roadblock

Description一个图,(n)个点(m)条边,求将一条边距离翻倍后使(1-n)最短路径增加的最大增量.SolDijstra.先跑一边最短路,然后枚举最短路,将路径翻倍然后跑Dijstra...因为不在最短路径上的边没用贡献,然后最短路径最长为(n-1)复杂度(O(nmlogm)Co... 查看详情

[bzoj2591][usaco2012feb]nearbycows

2591:[Usaco2012Feb]NearbyCowsTimeLimit:4Sec  MemoryLimit:128MBSubmit:149  Solved:89[Submit][Status][Discuss]Description FarmerJohnhasnoticedthathiscowsoftenmovebetweennearbyfi 查看详情

bzoj3942:[usaco2015feb]censoring

3942:[Usaco2015Feb]CensoringTimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 404  Solved: 221[Submit][Status][Discuss]DescriptionFarmerJohnhaspurchasedasubscriptiont 查看详情

bzoj3940[usaco2015feb]censoring

DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情

[bzoj]1631:[usaco2007feb]cowparty

1631:[Usaco2007Feb]CowPartyTimeLimit:5Sec  MemoryLimit:64MBSubmit:866  Solved:624[Submit][Status][Discuss]Description    农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X 查看详情

bzoj4412[usaco2016feb]circularbarn

先看成一条链for一遍找位置在for一遍算答案#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<cmath>usingnamespacestd;typedeflonglongLL;#def 查看详情

[bzoj1652][usaco06feb]treatsforthecows题解（区间dp）(代码片段)

[BZOJ1652][USACO06FEB]TreatsfortheCowsDescriptionFJhaspurchasedN(1<=N<=2000)yummytreatsforthecowswhogetmoneyforgivingvastamountsofmilk.FJsellsonetreatperdayandwantstomaximizethemoneyhereceivesov 查看详情

bzoj1651:[usaco2006feb]stallreservations专用牛棚

1651:[Usaco2006Feb]StallReservations专用牛棚TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 942  Solved: 544[Submit][Status][Discuss]DescriptionOhthosepickyN(1<=N< 查看详情

[bzoj]1611:[usaco2008feb]meteorshower流星雨

1611:[Usaco2008Feb]MeteorShower流星雨TimeLimit:5Sec  MemoryLimit:64MBSubmit:1654  Solved:707[Submit][Status][Discuss]Description去年偶们湖南遭受N年不遇到冰冻灾害，现在芙蓉哥哥则听说另一个骇人听闻的消息：一场流星雨即将袭击整个霸... 查看详情

bzoj1734:[usaco2005feb]aggressivecows愤怒的牛

1734:[Usaco2005feb]Aggressivecows愤怒的牛DescriptionFarmerJohnhasbuiltanewlongbarn,withN(2<=N<=100,000)stalls.Thestallsarelocatedalongastraightlineatpositionsx1,...,xN(0<=xi<=1,000,000,000).Hi 查看详情

bzoj3940[usaco2015feb]censoring*

bzoj3940[Usaco2015Feb]Censoring题意:有一个S串和一大堆T串，不断地在S串里找最早出现的T串，然后将其删除。S串≤100000，T串总长度≤100000。题解：对所有T串建AC自动机，然后同bzoj3942。注意，本题的AC自动机必须利用所有fail函数建成... 查看详情

bzoj1593:[usaco2008feb]hotel旅馆

1593:[Usaco2008Feb]Hotel旅馆TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 800  Solved: 441[Submit][Status][Discuss]Description奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作 查看详情

bzoj1593[usaco2008feb]hotel旅馆

1593:[Usaco2008Feb]Hotel旅馆TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 807  Solved: 447[Submit][Status][Discuss]Description奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作 查看详情

bzoj1676:[usaco2005feb]feedaccounting饲料计算

DescriptionFarmerJohnistryingtofigureoutwhenhislastshipmentoffeedarrived.Startingwithanemptygrainbin,heorderedandreceivedF1(1<=F1<=1,000,000)kilogramsoffeed.Regrettably,heisnotcertainexactlywhen 查看详情

bzoj3940:[usaco2015feb]censoring--ac自动机

3940:[Usaco2015Feb]CensoringTimeLimit: 10Sec  MemoryLimit: 128MBDescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterial 查看详情

bzoj1592[usaco2008feb]makingthegrade路面修整

1592:[Usaco2008Feb]MakingtheGrade路面修整TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 743  Solved: 514[Submit][Status][Discuss]DescriptionFJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的 查看详情