「IOI2016」外星人(斜率优化+wqs二分)
分析性质：
每个点x,y可以转化为一段区间,如果出现了\(x'\leq x,y'\leq y\)包含关系，那么可以忽略
所以可以转化为一些不相交的区间进行\(\text{dp}\)，代价为每个区间\((R-L+1)^2\)减去相交部分的平方(处理之后相交部分就只有\(i\)与\(i+1\)相交了)
预处理
rep(i,1,n) {
int x=rd()+1,y=rd()+1;
if(x>y) swap(x,y);
A[i]=(Node){x,y};
}
sort(A+1,A+n+1,[&](Node x,Node y){ return x.l<y.l||(x.l==y.l&&x.r>y.r); });
int cnt=0;
for(int i=1,maxr=0;i<=n;++i) if(A[i].r>maxr) maxr=A[i].r,A[++cnt]=A[i];
n=cnt;
首先我们考虑暴力的\(n^3\)做法
\(dp[i][j]\)表示当前搞定了前面\(i\)个区间，已经拍了\(j\)张，枚举区间转移
if(n<=500) {
memset(dp,63,sizeof dp);
dp[0][0]=0;
rep(i,1,n) {
rep(j,i,n) {
ll t=1ll*(A[j].r-A[i].l+1)*(A[j].r-A[i].l+1);
if(i>1 && A[i-1].r>=A[i].l)
t-=1ll*(A[i-1].r-A[i].l+1)*(A[i-1].r-A[i].l+1);
rep(d,0,k-1)
if(dp[i-1][d]<1e18) cmin(dp[j][d+1],dp[i-1][d]+t);
}
}
ll ans=1e18;
rep(i,1,k) cmin(ans,dp[n][i]);
printf("%lld\n",ans);
return 0;
}
\(O(n^2)\)做法：
很明显这个满足斜率优化的式子
而且这个二维dp满足四边形不等式
四边形不等式超级好写。。。
if(n<=4000) {
memset(dp,63,sizeof dp);
memset(g,-1,sizeof g);
rep(i,0,k) dp[0][i]=0;
rep(i,1,n) {
drep(j,k,1) {
int l=~g[i-1][j]?g[i-1][j]:1,r=~g[i][j+1]?g[i][j+1]:i;
ll res=1e18;
rep(d,l,r) {
ll t=1ll*(A[i].r-A[d].l+1)*(A[i].r-A[d].l+1);
if(d>1 && A[d-1].r>=A[d].l)
t-=1ll*(A[d-1].r-A[d].l+1)*(A[d-1].r-A[d].l+1);
if(res>dp[d-1][j-1]+t) res=dp[d-1][j-1]+t,g[i][j]=d;
}
dp[i][j]=res;
}
}
ll ans=1e18;
rep(i,1,k) cmin(ans,dp[n][i]);
printf("%lld\n",ans);
return 0;
}
\(\text{wqs}\)二分
发现对于\(dp[i][j]\)，有\(dp[i][j]-dp[i][j-1]\ge dp[i][j+1]-dp[i][j]\)，每次合并两个区间对于答案的贡献是递减的
满足斜率单调，所以可以二分斜率\(k\)
我们用一条直线\(y=kx+b\)去切这个函数，找到\(dp[n][j]-j\cdot k\)的最小值和所在的位置\(j_0\)，由此可以判断斜率是否太大或太小
这样我们把\(-k\)压进转移的代价里，就能省去\(j\)的那一维，同时维护\(g[i]\)表示\(dp[i]\)的最优决策选了\(g[i]\)个
降维之后无法使用四边形不等式，但是还是满足斜率优化的式子，注意每次转移的代价要\(-k\)
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define pb push_back
template <class T> inline void cmin(T &a,T b){ if(a>b) a=b; }
template <class T> inline void cmax(T &a,T b){ if(a<b) a=b; }
char IO;
template <class T=int> T rd(){
T s=0;
int f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=1e5+10;
int n,m,k,cnt;
struct Node{
int l,r;
bool operator < (const Node __) const {
return l<__.l || (l==__.l && r>__.r);
}
}A[N];
ll dp[N],w[N];
int g[N]; // 决策的分段数
ll sqr(ll x){ return x*x; }
int Q[N],L,R;
ll B[N];
void Check(ll c){
dp[0]=g[0]=0;
L=1,R=0;
rep(i,1,n){
ll t=-w[i]+sqr(A[i].l)+dp[i-1];
while(L<R &&
1ll*(t-B[R])*(A[Q[R]].l-A[Q[R-1]].l)<=1
ll*(B[R]-B[R-1])*(A[i].l-A[Q[R]].l)) R--;
Q[++R]=i,B[R]=t;
while(L<R &&
(B[L+1]-B[L])<2ll*(A[i].r+1)*(A[Q[L+1]].l-A[Q[L]].l) ) L++;
dp[i]=sqr(A[i].r+1)-2ll*(A[i].r+1)*A[Q[L]].l+B[L]+c;
g[i]=g[Q[L]-1]+1;
}
}
int main(){
n=rd(),m=rd(),k=rd();
rep(i,1,n) {
int x=rd()+1,y=rd()+1;
if(x>y) swap(x,y);
A[i]=(Node){x,y};
}
sort(A+1,A+n+1);
for(int i=1,maxr=0;i<=n;++i) if(A[i].r>maxr) maxr=A[i].r,A[++cnt]=A[i];
rep(i,2,n) w[i]=sqr(max(0,A[i-1].r-A[i].l+1)); // 相交部分的平方
n=cnt;
if(n<=k) {
ll ans=0;
rep(i,1,n) ans+=sqr((A[i].r-A[i].l+1));
rep(i,2,n) ans-=w[i];
printf("%lld\n",ans);
return 0;
}
ll l=0,r=1e13;
while(l<=r) {
ll mid=(l+r)>>1;
Check(mid);
if(g[n]>k) l=mid+1;
else r=mid-1;
}
Check(l);
printf("%lld\n",dp[n]-k*l);
}