学习了一下凸优化DP，感觉挺有意思的
首先把所有点对称到左下角，然后以每个点为顶点画等腰直角三角形，将被覆盖的点去掉，现在所有点从左上到右下横纵坐标都是递增的，设坐标为$(x_{1\cdots M},y_{1\cdots M})$
设$f_{j,i}$表示拍$j$次照片覆盖$i$个点的最少覆盖方格数，枚举最后一个矩形覆盖到之前的哪个点，有$f_{j,i}=\min\limits_{0\leq k\lt i}f_{j-1,k}+\left(y_i-x_{k+1}+1\right)^2-\max\left(y_i-x_{i+1}+1,0\right)^2$，最后减去的是和下一个矩形的重复部分
直接斜率优化可以$O(nk)$，还需要再快一些
凸优化用于解决一类“恰好选$k$个”的问题，在这题中，如果把$f_{j,i}$关于$j$的图像画出来，可以看出它的斜率不减（这我不会证，官方题解上也没讲怎么证，但一般可以通过打差分表猜出结论）
对于常数$C$，设$g_i=\min\limits_jf_{j,i}+jC$，将$f$用转移展开后再回代$g$的定义，我们得到$g_i=\min\limits_{0\leq k\lt i}g_k+\left(y_i-x_{k+1}+1\right)^2-\max\left(y_i-x_{i+1}+1,0\right)^2+C$，可以$O(n)$求
$g_i$是将$\Delta f_{j,i}$平移后取$f$的最小值得到的，所以当$C$增大时使$g$取到最小值的$j$会变小，于是我们可以通过二分找到一个$p$使得当$C=p$时，使$g_M$取得最小值的$j_1\geq k$，当$C=p+1$时，使$g_M$取得最小值的$j_2\leq k$
我们已经得到了$f_{j_1,M},f_{j_2,M}$，现在要求$f_{k,M}\left(k\in[j_2,j_1]\right)$，因为再把$\Delta f_{j,i}$往上平移$1$单位就会让最小值位置偏移，所以$\Delta f_{j_2+1\cdots j_1,M}$全部相等，也就是说$f_{j_2\cdots j_1,M}$是一条直线，所以可以直接算出$f_{k,M}$
总的来说，如果$f_{j,i}$是关于$j$的凸函数，难以求值却易求最值，那么可以考虑偏移$\Delta f_{j,i}$来改变最小值的位置，进而求出某个位置的值
总时间复杂度$O(n\log m)$，相当优美
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double du;
typedef vector<int> vi;
const du eps=1e-5;
template<class t>void gmax(t&a,t b){
if(a<b)a=b;
}
ll sqr(ll x){return x*x;}
struct line{
ll k,b;
int i;
line(ll k=0,ll b=0,int i=0):k(k),b(b),i(i){}
ll v(ll x){return k*x+b;}
}q[100010],u;
du its(line a,line b){
return(b.b-a.b)/(du)(a.k-b.k);
}
int x[100010],y[100010],M;
ll g[100010];
int b[100010];
int get(ll c){
int head,tail,i;
head=tail=1;
q[1]=line((x[1]-1)*-2,sqr(x[1]-1));
for(i=1;i<=M;i++){
while(head<tail&&its(q[head],q[head+1])<y[i]-eps)head++;
if(head<tail&&fabs(its(q[head],q[head+1])-y[i])<eps){
b[i]=min(q[head].i,q[head+1].i)+1;
head++;
}else
b[i]=q[head].i+1;
g[i]=q[head].v(y[i])+sqr(y[i])+c-sqr(max(y[i]-x[i+1]+1,0));
if(i<M){
u=line((x[i+1]-1)*-2,g[i]+sqr(x[i+1]-1),b[i]);
while(head<tail&&its(q[tail],q[tail-1])>its(q[tail],u))tail--;
q[++tail]=u;
}
}
return b[M];
}
int a[1000010];
ll inter(ll lc,ll rc,ll x){
ll lx,ly,rx,ry;
lx=get(lc);
ly=g[M]-lc*lx;
rx=get(rc);
ry=g[M]-rc*rx;
if(lx!=rx)
return(ly-ry)/(rx-lx)*(rx-x)+ry;
else
return ly;
}
ll take_photos(int n,int m,int k,vi r,vi c){
int i,t;
ll l,_r,mid,ans;
for(i=0;i<n;i++){
r[i]++;
c[i]++;
if(r[i]<c[i])
gmax(a[r[i]],c[i]);
else
gmax(a[c[i]],r[i]);
}
M=0;
t=0;
for(i=1;i<=m;i++){
if(a[i]>t){
M++;
x[M]=i;
y[M]=a[i];
t=a[i];
}
}
x[M+1]=m+1;
k=min(k,M);
#define r _r
l=0;
r=(ll)m*m;
ans=0;
while(l<=r){
mid=(l+r)>>1;
if(get(mid)>=k){
ans=mid;
l=mid+1;
}else
r=mid-1;
}
return inter(ans+1,ans,k);
#undef r
}
新的一年里要继续努力啊...