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;
}