bzoj4937 [CEOI2016]popeala

2018-11-04 19:16:51


$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;
}