欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一种优化带限制最优值动态规划的方法——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

题目描述
http://uoj.ac/problem/240

题解
假装他是道交互题。。。
首先把坐标点都沿对角线翻转到同一侧,然后只保留最外层的,剩下的显然没有意义。
暴力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;
}