💡题解与思路（含公式）

✨简要建模：

所有奶牛位置给定，总共在 $2 \times B$ 的矩形区域中；

每个牛棚只能是一个 完整的矩形区域，并且不能与其他牛棚重叠；

牛棚必须完整覆盖一些奶牛；

牛棚数不能超过 $K$；

最终目标是 使这些矩形的总面积最小。

🔍转化思路：

由于只有 2 行，每个奶牛的横坐标只有 1 或 2。可以将奶牛位置视为列坐标 $c_i$ 和行 $r_i$，每列最多有两个奶牛。

所以整个牧场相当于是一个一维列序列（长度 $B$）中的稀疏点集；

所有奶牛的位置可以排序，然后转换成一个长度最多为 $N$ 的 投影序列；

目标变为：用 $K$ 个区间来覆盖所有这些投影点，使得这些区间所构成的矩形的面积最小。

📐矩形面积的定义：

对于每一个选定的连续区间 $[l, r]$：

如果该区间中只出现过一行的奶牛（行号相同），那么面积是 $r - l + 1$；

如果区间中包含两个不同行的奶牛，那么面积是 $2 \cdot (r - l + 1)$；

🧠动态规划建模：

令：

$dp[i][k]$ 表示前 $i$ 个奶牛位置，使用 $k$ 个牛棚所需的最小面积。

转移方程：

𝑑 𝑝 [ 𝑖 ] [ 𝑘 ]

min ⁡ 𝑗 < 𝑖 ( 𝑑 𝑝 [ 𝑗 ] [ 𝑘 − 1 ] + 面积 ( [ 𝑗 + 1 , 𝑖 ] ) ) dp[i][k]= j<i min ​ (dp[j][k−1]+面积([j+1,i])) 其中：

$\text{面积}([j+1, i])$ 计算的是从奶牛位置 $j+1$ 到 $i$ 的一段连续区间所形成的矩形面积；

边界条件 $dp[0][0] = 0$，其余初始化为 $\infty$。

✅算法复杂度

时间复杂度：$O(N^2 \cdot K)$

空间复杂度：$O(N \cdot K)$

由于 $N \leq 1000,\ K \leq N$，所以该算法可通过。

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
inline int min(int a,int b)
{
	return a<b?a:b;
}
int pos[1010],n,k,b;
int s[1010],dp[1010][1010][4];
struct node
{
	int x,y;
	bool operator<(const node b)const
	{
		if(y==b.y)
			return x<b.x;
		return y<b.y;
	}
}a[1010];
int main()
{
	int i,j,l,cnt;
	while(scanf("%d%d%d",&n,&k,&b)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&a[i].x,&a[i].y);
		}
		cnt=1;
		sort(a+1,a+n+1);
		memset(s,0,sizeof(s));
		pos[cnt]=a[1].y;
		if(a[1].x==1)
			s[cnt]=0;
		else
			s[cnt]=1;
		for(i=2;i<=n;i++)
		{
			if(a[i].y==a[i-1].y)
			{
				s[cnt]=2;
				continue;
			}
			cnt++;
			pos[cnt]=a[i].y;
			if(a[i].x==1)
				s[cnt]=0;
			else
				s[cnt]=1;
		}
		//    for(i=1;i<=cnt;i++)
		//      printf("i %d s %d\n",i,s[i]);
		//  pos[0]=pos[1]-1;
		for(i=0;i<=cnt;i++)
			for(j=0;j<=k;j++)
				for(l=0;l<4;l++)
					dp[i][j][l]=inf;
		dp[0][0][2]=0;
		for(i=1;i<=cnt;i++)
		{
			for(j=1;j<=k;j++)
			{
				int tmp2;
				int tmp=min(min(dp[i-1][j-1][0],dp[i-1][j-1][1]),min(dp[i-1][j-1][2],dp[i-1][j-1][3]));
				if(j>=2)
					tmp2=min(min(dp[i-1][j-2][0],dp[i-1][j-2][1]),min(dp[i-1][j-2][2],dp[i-1][j-2][3]));
				if(s[i]==0)
				{
					dp[i][j][0]=min(tmp+1,min(dp[i-1][j][0],dp[i-1][j][3])+pos[i]-pos[i-1]);
					dp[i][j][2]=min(tmp+2,dp[i-1][j][2]+(pos[i]-pos[i-1])*2);
					dp[i][j][3]=min(dp[i-1][j][3]+2*(pos[i]-pos[i-1]),min(dp[i-1][j-1][0],dp[i-1][j-1][1])+pos[i]-pos[i-1]+1);
					if(j>=2)
						dp[i][j][3]=min(tmp2+2,dp[i][j][3]);
				}
				else if(s[i]==1)
				{
					dp[i][j][1]=min(tmp+1,min(dp[i-1][j][1],dp[i-1][j][3])+pos[i]-pos[i-1]);
					dp[i][j][2]=min(tmp+2,dp[i-1][j][2]+(pos[i]-pos[i-1])*2);
					dp[i][j][3]=min(dp[i-1][j][3]+2*(pos[i]-pos[i-1]),min(dp[i-1][j-1][0],dp[i-1][j-1][1])+pos[i]-pos[i-1]+1);
					if(j>=2)
						dp[i][j][3]=min(tmp2+2,dp[i][j][3]);
				}
				else
				{
					dp[i][j][2]=min(tmp+2,dp[i-1][j][2]+(pos[i]-pos[i-1])*2);
					dp[i][j][3]=min(dp[i-1][j][3]+2*(pos[i]-pos[i-1]),min(dp[i-1][j-1][0],dp[i-1][j-1][1])+pos[i]-pos[i-1]+1);
					if(j>=2)
						dp[i][j][3]=min(tmp2+2,dp[i][j][3]);
				}
				//   for(l=0;l<4;l++)
				//  printf("i %d j %d l %d dp %d\n",i,j,l,dp[i][j][l]);
			}
			
		}
		int ans=inf;
		for(j=0;j<4;j++)
		{
			ans=min(ans,dp[cnt][k][j]);
		}
		printf("%d\n",ans);
	}
}