一种优化带限制最优值动态规划的方法——wqs二分
程序员文章站
2022-06-01 16:34:36
...
一种优化带限制最优值动态规划的方法——wqs二分
前言
今年icpc南京站出了这么一道题。
一条轴上有n个点,每个点上有一个人。你要建最多k个商店,每个点上的人会去最近的商店,求每个人运动的距离和的最小值。
这东西显然满足决策单调性,一眼想到O(n*k)做法,然后发现n和k都是1e5级别的,遂gg。
所以本菜鸡队在南京站就7题滚粗了,最后挂机一小时,勉强拿了个金。
后来问了某dalao,某dalao不屑地表示,这题一个凸优化加一个斜率优化就好了。
凸优化是啥??我只知道AI的凸优化。。。
去搜了一下,了解了一个叫wqs二分的东西。
简述
假设没有k的限制,我们可以轻松地写出dp式并完成dp。
现在考虑这个限制,我们可以二分一个代价V,在dp的时候,每完成一次操作(如开一座商店)就需要付出V的代价。
对于本题,V越大,开一个商店的代价越大,开的商店数也就越少。
只要满足这个性质,我们就可以通过二分这个V,找到使得开的商店数<=k的最小的V,对应的dp值减去k*V就是答案。
什么时候可以使用这个算法呢?只要这个问题是个凸问题。
也就是说,我们定义g[x]表示操作x次的最大/最小收益,如果这个函数是个凸壳那么就可以这么做了。
例题
BZOJ2654 tree
题目描述
https://www.lydsy.com/JudgeOnline/problem.php?id=2654
题解
套个wqs二分。
二分每条白边对应的权值V。
然后跑个mst就好了。
代码
#include<bits/stdc++.h>
#define N 100010
#define inf 100
using namespace std;
int n,m,K,ans,fa[N];
struct node{
int a,b,c,col;
bool operator<(const node &p)const{
return c<p.c||(c==p.c&&col<p.col);
}
}e[N];
int find(int x)
{
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int cal(int mid,int &ans)
{
int sum=0,a,b;ans=0;
for(int i=1;i<=m;i++)
if(!e[i].col)e[i].c+=mid;
sort(e+1,e+m+1);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
a=find(e[i].a);b=find(e[i].b);
if(a!=b)fa[b]=a,ans+=e[i].c,sum+=!e[i].col;
}
for(int i=1;i<=m;i++)
if(!e[i].col)e[i].c-=mid;
return sum;
}
int main()
{
int a,b,c,d;
scanf("%d%d%d",&n,&m,&K);
for(int i=1;i<=m;i++)
scanf("%d%d%d%d",&a,&b,&c,&d),e[i]=(node){a+1,b+1,c,d};
int l=-inf,r=inf;
while(r-l>1)
{
int mid=l+r>>1;
if(cal(mid,ans)<K)r=mid-1;
else l=mid;
}
if(cal(r,ans)==K)printf("%d\n",ans-r*K);
else cal(l,ans),printf("%d\n",ans-l*K);
return 0;
}
UOJ240 【IOI2016】aliens
题解
假装他是道交互题。。。
首先把坐标点都沿对角线翻转到同一侧,然后只保留最外层的,剩下的显然没有意义。
暴力dp,f[i][j]=f[k][j-1]+(Y[i]-X[x+1]+1)^2-max(Y[i]-X[i+1]+1,0)^2
这东西决策单调,排个序后x坐标单调,显然可以斜率优化。
再加个wqs二分优化就可以过了
代码
#include<bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
int n,m,K,tot,X[N],Y[N],g[N],q[N];ll ans,f[N];
struct node{
int x,y;
bool operator<(const node &p)const{
return x<p.x||(x==p.x&&y>p.y);
}
}t[N];
ll sqr(ll x){return x*x;}
double cal(int k,int j){
return (sqr(X[j+1])-sqr(X[k+1])+f[j]-f[k]-2.0*X[j+1]+2.0*X[k+1])/2.0/(X[j+1]-X[k+1]);
}
int solve(ll V,ll &ans)
{
int l=1,r=1,x;
for(int i=1;i<=tot;i++)
{
while(l<r&&cal(q[l],q[l+1])<Y[i])l++;
x=q[l];f[i]=f[x]+sqr(Y[i]-X[x+1]+1)+V;g[i]=g[x]+1;
if(i<tot&&Y[i]>=X[i+1])f[i]-=sqr(Y[i]-X[i+1]+1);
while(l<r&&cal(q[r-1],q[r])>cal(q[r-1],i))r--;
q[++r]=i;
}
ans=f[tot]-K*V;return g[tot];
}
ll take_photos(int n,int m,int k,vector<int>r,vector<int>c)
{
K=k;
for(int i=0;i<n;i++)
t[i+1]=(node){min(r[i],c[i]),max(r[i],c[i])};
sort(t+1,t+n+1);
for(int i=1;i<=n;i++)
if(!tot||t[i].y>Y[tot])X[++tot]=t[i].x,Y[tot]=t[i].y;
ll L=0,R=(ll)m*m,mid;
while(R-L>1)
{
mid=L+R>>1;
if(solve(mid,ans)>k)L=mid+1;
else R=mid;
}
if(solve(L,ans)<=k)return ans;
solve(R,ans);return ans;
}