题意描述

Lazy Cows

给定一个 \(2\times b\) 的矩形，和 \(n\) 个矩形上的点。

要求你用 \(k\) 个矩形覆盖这 \(n\) 个点，使得每个点都被覆盖的前提下这些矩形的面积和最小。

算法分析

这道题的阶段性很强（按照目标点的纵坐标），但是状态不太好表示，于是想到状压。

首先将图改变一下，便于 DP：

将输入的奶牛按照位置从小到大排序。
在每个不同的位置（横坐标）记录一次。
如果这个位置（横坐标）的仅上面有奶牛，标记为 \(1\)；仅下面有奶牛，标记为 \(2\)；上下都有，标记为 \(3\)。

那么显然，改变之后的图中不同牛的数量 \(\leq n\)。

设计状态

设 \(f(i,j,0\)~\(4)\) 表示：到第 \(i\) 个牛的位置，用了 \(j\) 个牛舍，状态为 \(0\)~\(4\) 的最小面积。

解释一下状态：

表示上下都没有牛舍，这种情况仅存在于初始化。
表示上面有牛舍，下面没有。
表示上面没有牛舍，下面有。
表示上下都有牛舍，而且是同一个牛舍。
表示上下都有牛舍，而且是不同牛舍。

预处理

就是...，酱紫：

\(f(0,0,0)=0\)

\(f(1,1,1)=f(1,1,2)=1\)

\(f(1,1,3)=f(1,2,4)=2\)

\(f(其他)=INF\)

状态转移方程

然后我们按照情况讨论（推柿子）即可：

情况一：不增加牛舍数量

设 \(tmp=cow[i].x-cow[i-1].x\)（前后两列奶牛的横坐标之差）

\(f(i,j,1)=min(f(i-1,j,1),f(i-1,j,4))+tmp\)

\(f(i,j,2)=min(f(i-1,j,2),f(i-1,j,4))+tmp\)

\(f(i,j,3)=f(i-1,j,3)+2\times tmp\)

\(f(i,j,4)=f(i-1,j,4)+2\times tmp\)

解释一下：当不新增牛舍时，只能延长原本存在的牛舍，易得上面的递推式。

情况二：增加一个牛舍

设：

\(best1=min(f(i-1,j-1,1),f(i-1,j-1,2))\)

\(best2=min(f(i-1,j-1,3),f(i-1,j-1,4))\)

\(best=min(best1,best2)\)

\(f(i,j,1)=min(f(i,j,1),best+1)\)

\(f(i,j,2)=min(f(i,j,2),best+1)\)

\(f(i,j,3)=min(f(i,j,3),best+2)\)

\(f(i,j,4)=min(f(i,j,4),min(best1,f(i-1,j-1,4))+(tmp+1))\)

再来解释一下：首先的预处理就是为了方便处理，仅是个人习惯不用过多纠结。

如果能够增加一个牛舍，那么对于状况 \(1,2,3\) 均可以直接原地增加一个牛舍，不用管前面是什么状况。

但是对于状况 \(4\)，只能增加一个牛舍的情况将十分尴尬，只能从前面延长一个牛舍，再本地新增一个牛舍。

显然只能从上一次的状况 \(1,2,4\) 推来。

情况三：增加两个牛舍

\(f(i,j,4)=min(f(i,j,4),min\{f(i,j-2,1\)~\(4)\}+2)\)

显然，只有情况四需要新增两个牛舍（其他一个就够了），所以易得上方程。

答案统计

易得：

\(ans=min_{1\leq p\leq 4}\{f(n,k,p)\}\)

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cmath>

#define N 1010

#define INF 0x3f3f3f3f

using namespace std;

int n,k,b,cnt=0;

int f[N][N][10];

struct node{

	int x,y;

}a[N];

struct Cow{

	int x,t;

}cow[N];

int read(){

	int x=0,f=1;char c=getchar();

	while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();

	while(c>='0' && c<='9') x=x*10+c-48,c=getchar();

	return x*f;

}

bool cmp(node a,node b){

	if(a.x!=b.x) return a.x<b.x;

	return a.y<b.y;

}

void build(){

	for(int i=1;i<=n;i++){

		if(a[i].x==a[i-1].x)

			cow[cnt].t=3;

		else cow[++cnt].t=a[i].y,cow[cnt].x=a[i].x;

	}

	return;

}

void dp(){

	memset(f,0x3f,sizeof(f));

	f[0][0][0]=0;

	if(cow[1].t==1) f[1][1][1]=1;

	else if(cow[1].t==2) f[1][1][2]=1;

	f[1][1][3]=f[1][2][4]=2;

	for(int i=2;i<=cnt;i++){

		for(int j=1;j<=k;j++){

			int tmp=cow[i].x-cow[i-1].x;

			if(cow[i].t==1) f[i][j][1]=min(f[i-1][j][1],f[i-1][j][4])+tmp;

			if(cow[i].t==2) f[i][j][2]=min(f[i-1][j][2],f[i-1][j][4])+tmp;

			f[i][j][3]=f[i-1][j][3]+2*tmp;

			f[i][j][4]=f[i-1][j][4]+2*tmp;

			if(j==1) continue;

			int best1=min(f[i-1][j-1][1],f[i-1][j-1][2]);

			int best2=min(f[i-1][j-1][3],f[i-1][j-1][4]);

			int best=min(best1,best2);

			if(cow[i].t==1) f[i][j][1]=min(f[i][j][1],best+1);

			if(cow[i].t==2) f[i][j][2]=min(f[i][j][2],best+1);

			f[i][j][3]=min(f[i][j][3],best+2);

			f[i][j][4]=min(f[i][j][4],min(f[i-1][j-1][4],best1)+(tmp+1));

			if(j==2) continue;

			f[i][j][4]=min(f[i][j][4],min(min(f[i-1][j-2][1],f[i-1][j-2][2]),min(f[i-1][j-2][3],f[i-1][j-2][4]))+2);

		}

	}

}

int main(){

	//freopen("lazy.in","r",stdin);

	//freopen("lazy.out","w",stdout);

	n=read(),k=read(),b=read();

	for(int i=1;i<=n;i++)

		a[i].y=read(),a[i].x=read();

	sort(a+1,a+n+1,cmp);

	build();

	dp();

	printf("%d\n",min(min(f[cnt][k][1],f[cnt][k][2]),min(f[cnt][k][3],f[cnt][k][4])));

	//fclose(stdin);fclose(stdout);

	return 0;

}

完结撒花

巴特西

POJ2430 Lazy Cows