bzoj4937 [CEOI2016]popeala

$cwbc$的膜你赛题 首先写出暴力$dp$ $f[i][j]$表示前$i$个测试点分成$j$个区间的最小得分总和 $O(nm^3)$预处理出$w(l,r)$表示把$[l,r]$划分成一段区间的得分 然后就可以$O(m^2S)$转移了 $f[i][j]=min\left\{f[k][j-1]+w(k+1,r)\right\},k∈[0,i)$ ------------ 发现可以更快地预处理$w(l,r)$ 固定左端点$l$，向右移动右端点 每向右移动一个点，可以$O(n)$维护还有几个人可以通过这个测试点 然后乘以区间总分就可以，复杂度$O(nm^2)$ ------------ 用$a$数组保存测试点分值的前缀和 设$A(l,r)$表示能通过$[l,r]$测试点的人数 那么转移可以写成：$f[i][j]=min\left\{f[k][j-1]+A(k+1,i)*(a[i]-a[k])\right\},k∈[0,i)$ 因为$n<=50$，所以$A$的范围其实是很小的 考虑将转移按照$A$分类，在每一类中$A$是一个常数 那么有$f[i][j]=A*a[i]+min\left\{f[k][j-1]-A*a[k]\right\},k∈[0,i)$ 可以发现，当常数$A$固定时，满足$A(k+1,i)=A$的$k$一定是一个区间 并且当$i$增大时，这个区间的左右端点都会向右移动 所以相当于对一些左右端点单调不降的区间取区间最小值 可以用单调队列来实现 ------------ 具体做法：对每个$i$和每个$A$处理出对应的$k$的区间，按$j$从小到大一层层转移。在每一层中，按$A$分类，每一类可以做到$O(m)$，总复杂度$O(nmS)$ 代码好难写啊$Orz$ 而且$bzoj$好像不能在$memset$里面用$127$？ 只能用$for$循环初始化 注意：因为这$S$个答案相互独立，所以每一次都要初始化！并且不能用一般的滚动数组，否则会影响后面的答案 ``` #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=55,M=2e5+5,inf=2e9; char s[N][M]; int n,m,T,a[M],f[M],g[M],L[N][M],R[N][M],q[M<<2],w[M<<2],pre[N]; inline void del(int x,int y) { for (int i=1;i<=n;i++) if (q[i]==x){for (int j=i;j<n;j++) q[j]=q[j+1]; break;} q[n]=y; } int main() { scanf("%d%d%d",&n,&m,&T); for (int i=1,x;i<=m;i++) scanf("%d",&x),a[i]=a[i-1]+x; for (int i=1;i<=n;i++) scanf("%s",s[i]+1); for (int j=1;j<=m;j++) { for (int i=1;i<=n;i++) if (s[i][j]=='0') del(pre[i],j),pre[i]=j; L[n][j]=q[n]+1,R[n][j]=j; for (int i=1;i<n;i++) L[i][j]=q[i]+1,R[i][j]=q[i+1]; L[0][j]=1,R[0][j]=q[1]; } for (int i=1;i<=m;i++) f[i]=inf; for (int k=1;k<=T;k++) { for (int i=0;i<=m;i++) g[i]=inf; for (int i=0;i<=n;i++) { int h=1,t=0,r=-1; for (int j=1;j<=m;j++) { while (r<R[i][j]-1) { ++r; int cur=f[r]-i*a[r]; while (h<=t&&cur<=w[t]) --t; q[++t]=r; w[t]=cur; } while (h<=t&&q[h]<L[i][j]-1) ++h; if (h<=t) g[j]=min(g[j],w[h]+i*a[j]); } } memcpy(f,g,sizeof(g)); printf("%d\n",f[m]); } return 0; } ```