自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

搬运于2025-08-24 22:56:30，当前版本为作者最后更新于2024-03-25 15:02:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1.9 小时通关金组，你值得拥有！

考虑设状态进行动态规划！

设 $f_{x,y}$ 表示第一个数组划分到 $x$，第二个数组划分到 $y$ 的方案数。

此时如果在上下两个数组同时选定新的区间，这样是 $O(n^4)$ 的，无法通过。

考虑先走第二个数组，即枚举 $x,y$，将所有 $f_{x,p},p<y$ 的区间 $(p,y]$ 的权值提出来，排序，再枚举 $x$ 走到 $z$，用 $(x,z]$ 的权值进行二分即可。

这样的时间复杂度是 $O(n^3\log n)$ 的，无法通过。

实际上，这里的二分和排序都很慢，但也差不多，表现起来就和卡常了一样，不过 USACO 是不会卡常的，所以考虑进一步优化。

我们想到，如果能将这里的二分改成双指针就好了！

但这样会多排序一次，依旧无法接受。

然而，我们发现，这里每次排序的值对于 $x,y$ 来说都是一样的，所以可以对于每个 $x,y$ 再预处理时进行排序，只有 $O(n^2\log n)$ 的复杂度，转移的时候双指针就好。

总时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$，可以通过：

ll mk(int x,int y){
    return LL(1e12)*x/y;
}
using D1=pair<ll,int>;
int n,a[N],b[N],bt,rt,f[505][505];
pair<ll,int>rp[N];
D1 h[505][505];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int i,j,k,l,r,x,y,z;
    cin>>n;
    for(x=1;x<=n;++x)cin>>a[x],a[x]+=a[x-1];
    for(x=1;x<=n;++x)cin>>b[x],b[x]+=b[x-1];
    for(y=0;y<n;++y){
        for(k=y+1;k<=n;++k)h[y][k-y]={mk(b[k]-b[y],k-y),k};
        sort(h[y]+1,h[y]+n-y+1);
    }
    f[0][0]=1;
    for(x=1;x<=n;++x){
        for(l=0,rt=0;l<x;++l)rp[l]={mk(a[x]-a[l],x-l),l};
        sort(rp,rp+x);
        for(y=0;y<n;++y){
            for(i=1,l=k=0;i<=n-y;++i){
                while(l<x&&rp[l].first<=h[y][i].first)add(k,f[rp[l++].second][y]);
                add(f[x][h[y][i].second],k);
            }
        }
    }
    printf("%d\n",f[n][n]);
    return 0;
}

题外话，赛时刚开始为了卡常使用 long long 来存浮点数来卡常，欢迎提出 Hack 数据。