首页 > 代码库 > bzoj4760[USACO2017 Jan]Hoof,Paper,Scissors
bzoj4760[USACO2017 Jan]Hoof,Paper,Scissors
题意:玩n次剪刀石头布,对方每次出什么已经知道了.你出的招数必须是连续的几段(不能超过k+1段),问你最多赢几次.(n<=100000,k<=20)
正常做法:f[i][j][k]表示前i次,分j段,最后一次出的是k(k=0,1,2)时最多赢几次,可以O(nk)解决,转移时看最近一次有没有新分一段即可.
智障做法:我们同样定义f[i][j][k]表示前i次,分j段,最后一次出的是k时最多赢几次,但转移的时候考虑最近的一段,也就是枚举最近的一段是从哪里开始的,那么这就变成了1D1D动态规划,打表观察到决策单调性,可以大力写一个决策单调性O(nlognk)解决,强行多一个log也可以过
讲道理决策单调性还是很好写的
#include<cstdio> #include<algorithm> using namespace std; const int maxn=100005; int sum[3][maxn]; int f[22][maxn][3]; void solve(int l,int r,int L,int R,int j,int t){//printf("%d %d %d %d %d\n",l,r,L,R,j); if(l>r)return; int mid=(l+r)>>1,g=0,tmp=0; for(int i=L;i<=R&&i<=mid;++i){ tmp=sum[t][mid]-sum[t][i]; for(int k=0;k<3;++k) if(tmp+f[j-1][i][k]>f[j][mid][t]){ f[j][mid][t]=f[j-1][i][k]+tmp;g=i; } } solve(l,mid-1,L,g,j,t);solve(mid+1,r,g,R,j,t); } int main(){ int n,k; scanf("%d%d",&n,&k);k++; char buf[3]; for(int i=1;i<=n;++i){ scanf("%s",buf); for(int k=0;k<3;++k)sum[k][i]=sum[k][i-1]; if(buf[0]==‘H‘)sum[0][i]++; else if(buf[0]==‘S‘)sum[1][i]++; else sum[2][i]++; } for(int j=1;j<=k;++j){ for(int t=0;t<3;++t)solve(1,n,0,n-1,j,t); }//printf("%d\n",f[1][4]); int ans=0; for(int i=1;i<=k;++i)for(int t=0;t<3;++t)ans=max(ans,f[i][n][t]); printf("%d\n",ans); return 0; }
bzoj4760[USACO2017 Jan]Hoof,Paper,Scissors
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。