首页 > 代码库 > bzoj4937: [Ceoi2016]popeala
bzoj4937: [Ceoi2016]popeala
Description
你办了一场比赛，有n给人参加，只有一道题，有m个数据点，标号为1~m，每个测试点都有一个分数a[i]。现在所
有选手已经提交了程序并且测评完了，你知道每个人都能通过哪些测试点。你现在要安排捆绑测试的方式，把数据
点划分为若干个连续的区间，每个区间至少有一个测试点。每个区间只要有一个测试点错误就不会得分，如果所有
点都正确得分为所有测试点的分数的和。你的目的是最小化所有人的得分和。你需要对1<=i<=S，输出当把所有测
试点划分为i组时，最小的所有人分数和。
Input
第一行三个整数n,m,S
接下来一行m个整数，代表a[i]
接下来n行每行一个长度为m的01串，代表第i个人是否通过了第j个测试点
n<=50
m<=20000
S<=min(50,m)
a[i]<=10000,sigma a[i]*n<=2000000000
Output
S行，每行一个整数，代表当划分为i个捆绑测试点时所有人分数和的最小值
每次dp多分一段，dp时状态转移方程可分为O(n)段，且段之间的分界单调右移，用单调队列维护每个段的最值即可转移，时间复杂度O(nmS)
#include<bits/stdc++.h>const int inf=0x7f7f7f7f;int _(){ int x=0,c=getchar(); while(c<48)c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x;}void mins(int&a,int b){if(a>b)a=b;}int min(int a,int b){return a<b?a:b;}int n,m,q,a[20007],p0[55];char s[55][20007];int f[20007],t[20007],g[20007];struct Q{ int q[20007],ql,qr,id; void clr(){ql=1,qr=0;} void ins(int x){ if(f[x]==inf)return; int v=f[x]-a[x]*id; while(ql<=qr){ int y=q[qr]; if(f[y]-a[y]*id>=v)--qr; else break; } q[++qr]=x; } void del(int x){ if(ql<=qr&&q[ql]==x)++ql; } int gmn(int w){ if(ql>qr)return inf; int x=q[ql]; return f[x]+(a[w]-a[x])*id; }}qs[55];int main(){ n=_(),m=_(),q=_(); for(int i=1;i<=m;++i)a[i]=_()+a[i-1]; for(int i=1;i<=n;++i){ scanf("%s",s[i]+1); qs[i].id=i; for(int j=1;j<=m&&s[i][j]==‘1‘;++j)f[j]+=a[j]; } printf("%d\n",f[m]); for(int i=2;i<=q;++i){ for(int j=0;j<=n;++j){ p0[j]=0; qs[j].clr(); } f[0]=inf; for(int j=1;j<=m;++j){ qs[t[j]=n].ins(j-1); for(int k=1;k<=n;++k)if(s[k][j]==‘0‘){ for(int z=p0[k]+1;z<=j;++z){ qs[ t[z]].del(z-1); qs[--t[z]].ins(z-1); } p0[k]=j; } g[j]=inf; for(int k=0;k<=n;++k)mins(g[j],qs[k].gmn(j)); } memcpy(f,g,sizeof(int)*(m+1)); printf("%d\n",f[m]); } return 0;}
bzoj4937: [Ceoi2016]popeala
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。