题⽬8：Lazy Cow 懒惰的⽜
题⽬描述
这是⼀个炎热的夏⽇。懒洋洋的奶⽜⻉茜想将⾃⼰放置在⽥野中的某个位置， 以便可以在短距离内尽
可能多地吃到美味的草。⻉茜所在的⽥野中共有 N ⽚草 地，我们可以将⽥野视作⼀个⼀维数轴。 第 i
⽚草地中包含 gi 单位的⻘草，位置 坐标为 xi。不同草地的位置不同。⻉茜想选取⽥野中的某个点作为
她的初始位置（可 能是某⽚草地所在的点）。只有⼀⽚草地与她的初始位置的距离不超过 K 时，⻉ 茜
才能吃到那⽚草地上的草。
如果⻉茜选择最佳初始位置，请确定她可以吃到的⻘ 草最⼤数量。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
struct lenka
{
long long x,y;
}a[10000],b[10000];
int cmp(const lenka& x,const lenka& y)
{
if(x.y==y.y)return x.x<y.x;
return x.y<y.y;
}
long long d[1001][1001][5];
int main()
{
int n,k,L;
while(cin>>n>>k>>L)
{
for(int i=0;i<n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);
sort(a,a+n,cmp);
int MAX=1;
for(int i=0;i<n;) //把不同列的选出来
{
if(i+1<n&&a[i+1].y==a[i].y)//找到同一列的
{
b[MAX].x=a[i].y;
b[MAX++].y=3;
i+=2;
}
else
{
b[MAX].x=a[i].y;
b[MAX++].y=a[i].x;
i++;
}
// printf("第%lld列 %lld行\n",b[MAX-1].x,b[MAX-1].y);
}
memset(d,0x3f3f3f3f,sizeof d);
d[0][0][3]=0;
for(int i=1;i<MAX;i++)
{
for(int j=1;j<=k;j++)
{
long long A,B;
A=min(min(d[i-1][j-1][1],d[i-1][j-1][2]),min(d[i-1][j-1][3],d[i-1][j-1][4]));
if(j>=2)B=min(min(d[i-1][j-2][1],d[i-1][j-2][2]),min(d[i-1][j-2][3],d[i-1][j-2][4]));
if(b[i].y==1) //只有第一行有牛
{
d[i][j][1]=min(d[i][j][1],A+1);
d[i][j][1]=min(d[i][j][1],d[i-1][j][1]+b[i].x-b[i-1].x);//延长之前的barn
d[i][j][1]=min(d[i][j][1],d[i-1][j][4]+b[i].x-b[i-1].x);
}
else if(b[i].y==2) //只有第二行有牛
{
d[i][j][2]=min(d[i][j][2],A+1);
d[i][j][2]=min(d[i][j][2],d[i-1][j][2]+b[i].x-b[i-1].x);
d[i][j][2]=min(d[i][j][2],d[i-1][j][4]+b[i].x-b[i-1].x);
}
d[i][j][3]=min(d[i][j][3],A+2);
d[i][j][3]=min(d[i][j][3],d[i-1][j][3]+2ll*(b[i].x-b[i-1].x));
d[i][j][4]=min(min(d[i-1][j-1][1],d[i-1][j-1][2])+b[i].x-b[i-1].x+1,d[i-1][j][4]+2ll*(b[i].x-b[i-1].x));
if(j>=2)d[i][j][4]=min(d[i][j][4],B+2);
}
}
cout<<min(min(d[MAX-1][k][1],d[MAX-1][k][2]),min(d[MAX-1][k][3],d[MAX-1][k][4]))<<endl;
}
return 0;
}