思路
首先想到一个\(n^{4}\)的dp,观察数据范围,发现这应该是一个\(n^{3}\)的算法,考虑如何优化。首先把转移方程写出来\(dp_{i,j}=\sum_{0\le ii\le i-1,0\le jj\le j-1,\overline{a_{ii+1}...a{i}}\le \overline{b_{jj+1}...b{j}}} dp_{ii,jj}\),发现都不太好优化。首先枚举\(i\),\(j\)的两维是不可能被优化的,然后考虑枚举\(jj\),然后找到所有满足条件的\(ii\)的和就可以了。如果我们枚举了jj,就可以得出\(\overline{b_{jj+1}...b{j}}\),此时就是要求满足\(\overline{a_{ii+1}...a{i}}\le \overline{b_{jj+1}...b{j}}\)的\(ii\)显然这样可以二分,然后与处理一下即可做到\(n^{3}\log n\)。发现瓶颈在二分上,考虑怎样能把二分去掉。发现如果两个平均数都是单调的,那么我们就可以使用双指针了。
实现
思路大概想好了,首先我们枚举了\(i,j,jj\),然后第三层循环里面是一个双指针。
比如当前的ii(红色),jj(蓝色),做到了这里,那么这个蓝色就可以和箭头指向的红色的前面(包含这个)产生贡献。而这个是可以用前缀和优化的。然后这样我们的实现也清楚了,就是搞出sum[j][i]表示当\(jj=j\)时,前i的a的平均数产生的贡献(可以看代码理解一下)然后就可以了
我也不知道我这个大常数选手怎么没被卡
#include<bits/stdc++.h>
#define for1(i,a,b) for( int i=(a);i<=(b);i++)
#define for2(i,a,b) for( int i=(a);i<(b);i++)
#define for3(i,a,b) for( int i=(a);i>=(b);i--)
#define for4(i,a,b) for( int i=(a);i>(b);i--)
#define mx(a,b) max(a,b)
#define mn(a,b) min(a,b)
#define puba push_back
#define mem(a) memset((a),0,sizeof((a)))
#define int long long
using namespace std;
const int mod=1e9+7;
int n,a[505],b[505],dp[505][505];
int suma[505],sumb[505],sum[505][505];
struct node{
int l,sum;
}ai[505][505],bi[505][505];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for1(i,1,n){
cin>>a[i];
suma[i]=suma[i-1]+a[i];
}for1(i,1,n){
cin>>b[i];
sumb[i]=sumb[i-1]+b[i];
}
for1(j,1,n){
for1(i,1,j){
ai[j][i].sum=(suma[j]-suma[i-1]);
bi[j][i].sum=(sumb[j]-sumb[i-1]);
ai[j][i].l=bi[j][i].l=i;
}
}
for1(i,1,n){
for1(j,1,i){
for1(k,1,i-1){
if(ai[i][k].sum*(i-ai[i][k+1].l+1)>ai[i][k+1].sum*(i-ai[i][k].l+1)){
swap(ai[i][k],ai[i][k+1]);
}if(bi[i][k].sum*(i-bi[i][k+1].l+1)>bi[i][k+1].sum*(i-bi[i][k].l+1)){
swap(bi[i][k],bi[i][k+1]);
}
}//最低级的冒泡排(懒)
}//还有一个原因是这里为了保证精度需要移项,cmp函数不太好写
}
dp[0][0]=1;
for1(i,1,n){
for1(j,1,n){
for1(k,1,i){
sum[j][k]=(sum[j][k-1]+dp[ai[i][k].l-1][j-1])%mod;
}//搞出sum
}
for1(j,1,n){
int ii=1;
for1(jj,1,j){
while(ai[i][ii].sum*(j-bi[j][jj].l+1)<=bi[j][jj].sum*(i-ai[i][ii].l+1)&&ii<=i) ii++;
dp[i][j]=(dp[i][j]+sum[bi[j][jj].l][ii-1])%mod;//双指针出的是第一个不满足要求的,所以是ii-1
}
}
}
cout<<dp[n][n];
return 0;
}
标签:ai,sum,bi,jj,for1,505,P10282
From: https://www.cnblogs.com/wuhupai/p/18141731