USACO open 2024 金组 T3

· · 题解

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 数据。