# Poj Solution 2430

```http://poj.org/problem?id=2430

#include<iostream>
#include"algorithm"
using namespace std;

const int size=1010;
int ans[size][size][4];
int best[size][size];

int n,m,b,nn;
enum{both,up,down,sep};
const int inf=99999999;

struct point
{
int y;
int x;
int s;
}pt[size],p[size];

bool cmp(point a,point b)
{
return a.x<b.x;
}

void init()
{
int i,j;
cin>>n>>m>>b;

for(i=0;i<n;i++)
{
cin>>pt[i].y>>pt[i].x;
pt[i].s=0;
}

std::sort(pt,pt+n,cmp);

p[0].x=p[0].y=0;
p[1]=pt[0];
for(i=1,j=2;i<n;i++)
{
if(pt[i].x==pt[i-1].x)
p[j-1].s=1;
else p[j++]=pt[i];
}
nn=n;
n=j;

}

void doit()
{
int i,j,t,k;

for(j=0;j<=m;j++)
{
for(k=0;k<4;k++)
ans[0][0][k]=0;
best[0][j]=0;
}

for(i=1;i<n;i++)
{
for(k=0;k<4;k++)
ans[i][0][k]=inf;
best[i][0]=inf;

for(j=1;j<=m;j++)
{
ans[i][j][up]=ans[i][j][down]=best[i-1][j-1]+1;
if(p[i].y==p[i-1].y && (t=ans[i-1][j][p[i].y]+p[i].x-p[i-1].x) < ans[i][j][p[i].y] )
ans[i][j][p[i].y] = t;
if( (t=ans[i-1][j][sep]+p[i].x-p[i-1].x) < ans[i][j][p[i].y] )
ans[i][j][p[i].y] = t;

ans[i][j][both]=best[i-1][j-1]+2;
if( (t=ans[i-1][j][both]+(p[i].x-p[i-1].x)*2) <ans[i][j][both] )
ans[i][j][both] = t;

if(j==1)ans[i][j][sep]=inf;
else
{
ans[i][j][sep]=best[i-1][j-2]+2;
if( (t=ans[i-1][j-1][up]+p[i].x-p[i-1].x+1) < ans[i][j][sep] )
ans[i][j][sep] = t;
if( (t=ans[i-1][j-1][down]+p[i].x-p[i-1].x+1) < ans[i][j][sep] )
ans[i][j][sep] = t;
if( (t=ans[i-1][j][sep]+(p[i].x-p[i-1].x)*2 ) < ans[i][j][sep] )
ans[i][j][sep] = t;
}

if(p[i].s)
ans[i][j][up]=ans[i][j][down]=inf;
else
ans[i][j][3-p[i].y]=inf;

best[i][j]=inf;
for(k=0;k<4;k++)
if(ans[i][j][k]<best[i][j])
best[i][j]=ans[i][j][k];
}
}
}
int main()
{
init();
doit();

cout<<best[n-1][m]<<endl;

return 0;
}
```
This entry was posted in poj. Bookmark the permalink.