标签：va Last cl int hard long ++ Nanami cr
- 如果从前缀和的视角考察题目中需要统计的信息，那么子段和=x等价于s[r]-s[l-1]=x
- 于是我们虽然不能O(1)地求出w(l,r)，但是可以O(1)地将已知的w(l,r)扩展
- w(l,r)是一个非常明显的满足“包含大于等于交叉”的四边形不等式的函数，除此之外，通过打表找规律，也可以发现DP有决策单调性
- 决策单调性优化有两种形式：分治法和单调队列法，由于本题中w(l,r)不能O(1)地求出，因此我们选择分治法
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[100005],s[100005];
long long f[100005][25],va,cl,cr;
int x;
unordered_map<int,int>q;
long long val(int l,int r)
{
while(l<cl)
{
cl--;
va+=q[x+s[cl-1]];
q[s[cl-1]]++;
}
while(r>cr)
{
cr++;
va+=q[s[cr]-x];
q[s[cr]]++;
}
while(l>cl)
{
q[s[cl-1]]--;
va-=q[x+s[cl-1]];
cl++;
}
while(r<cr)
{
q[s[cr]]--;
va-=q[s[cr]-x];
cr--;
}
return va;
}
void calc(int l,int r,int j,int jl,int jr)
{
if(l>r)
{
return;
}
int p;
int mid=(l+r)>>1;
for(int i=min(mid-1,jr);i>=jl;i--)
{
long long va=val(i+1,mid);
if(f[i][j-1]+va<f[mid][j])
{
p=i;
f[mid][j]=f[i][j-1]+va;
}
}
calc(l,mid-1,j,jl,p);
calc(mid+1,r,j,p,jr);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>n>>k>>x;
s[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
memset(f,0x3f,sizeof(f));
f[0][0]=0;
cl=1,cr=0;
q[0]++;
for(int i=1;i<=n;i++)
{
f[i][1]=val(1,i);
}
for(int j=2;j<=k;j++)
{
calc(j,n,j,j-1,n);
}
cout<<f[n][k]<<endl;
return 0;
}
标签：va,
Last,
cl,
int,
hard,
long,
++,
Nanami,
cr
From： https://www.cnblogs.com/watersail/p/18278501