#include <iostream>
using namespace std;
struct cow
{
      int n;
      int ud;
}dd[1005],td[1005];
int cmp(cow a,cow b)
{
     if(a.n==b.n)
       return a.ud<b.ud;
     return a.n<b.n;
}
int INF=30000005;
int dp[1005][1005][4];
int main()
{
     int n,k,b;
     int i,j,w;
     int tb;
     while(scanf("%d %d %d",&n,&k,&b)==3)
     {
         for(i=1;i<=n;i++)
           scanf("%d %d",&dd[i].ud,&dd[i].n);
         sort(dd+1,dd+1+n,cmp);
         tb=0;
         int pre=0;
         for(i=1;i<=n;i++)
           {
               if(pre!=dd[i].n)
                 {
                     tb++;
                     pre=dd[i].n;
                     td[tb]=dd[i];
                 }
               else
                     td[tb].ud=3;
           }
        for(i=1;i<=tb;i++)
           for(w=1;w<=k+4;w++)
            for(j=0;j<=3;j++)
              dp[i][w][j]=INF;
         if(td[1].ud==3)
         {
             dp[1][1][0]=2;
             dp[1][2][1]=2;
         }
         if(td[1].ud==2)
         {
             dp[1][1][0]=2;


             dp[1][1][3]=1;
         }
         if(td[1].ud==1)
         {
             dp[1][1][0]=2;
             dp[1][1][2]=1;
         }
         // 0 上下 1上   下 2 上 3 下
         for(i=1;i<tb;i++)
           for(w=1;w<=k;w++)
            {
             if(dp[i][w][0]!=INF)
             {
               dp[i+1][w][0]=min(dp[i][w][0]+(td[i+1].n-td[i].n)*2,dp[i+1][w][0]);
               dp[i+1][w+1][0]=min(dp[i][w][0]+2,dp[i+1][w+1][0]);
               dp[i+1][w+2][1]=min(dp[i][w][0]+2,dp[i+1][w+2][1]);
               if(td[i+1].ud==1)
                 dp[i+1][w+1][2]=min(dp[i][w][0]+1,dp[i+1][w+1][2]);
                if(td[i+1].ud==2)
                 dp[i+1][w+1][3]=min(dp[i][w][0]+1,dp[i+1][w+1][3]);
             }
             if(dp[i][w][1]!=INF)
             {
               dp[i+1][w][1]=min(dp[i][w][1]+(td[i+1].n-td[i].n)*2,dp[i+1][w][1]);
             //   printf("%d %d %d\n",dp[i+1][w][1],i+1,w);
               dp[i+1][w+1][0]=min(dp[i][w][1]+2,dp[i+1][w+1][0]);
               dp[i+1][w+2][1]=min(dp[i][w][1]+2,dp[i+1][w+2][1]);
               if(td[i+1].ud==1)
                 {
                     dp[i+1][w][2]=min(dp[i+1][w][2],dp[i][w][1]+(td[i+1].n-td[i].n));


                     dp[i+1][w+1][2]=min(dp[i][w][1]+1,dp[i+1][w+1][2]);
                 }
              if(td[i+1].ud==2)
                {
                     dp[i+1][w][3]=min(dp[i+1][w][3],dp[i][w][1]+(td[i+1].n-td[i].n));
                     dp[i+1][w+1][3]=min(dp[i][w][1]+1,dp[i+1][w+1][3]);
                }
             }
             if(dp[i][w][2]!=INF)
             {
               dp[i+1][w+1][0]=min(dp[i][w][2]+2,dp[i+1][w+1][0]);
               dp[i+1][w+2][1]=min(dp[i][w][2]+2,dp[i+1][w+2][1]);
               if(td[i+1].ud==1)
               {
                 dp[i+1][w][2]=min(dp[i+1][w][2],dp[i][w][2]+(td[i+1].n-td[i].n));
             //     printf("%d %d %d\n",dp[i+1][w][2],i+1,w);
                 dp[i+1][w+1][2]=min(dp[i][w][2]+1,dp[i+1][w+1][2]);
               }
                if(td[i+1].ud==2)
                {
                 dp[i+1][w+1][1]=min(dp[i+1][w+1][1],dp[i][w][2]+(td[i+1].n-td[i].n)+1);
                 dp[i+1][w+1][3]=min(dp[i][w][2]+1,dp[i+1][w+1][3]);
                }
               if(td[i+1].ud==3)
               {
                     dp[i+1][w+1][1]=min(dp[i+1][w+1][1],dp[i][w][2]+(td[i+1].n-td[i].n)+1);


                //          printf("%d %d %d\n",dp[i+1][w+1][1],i+1,w+1);
               }
             }
             if(dp[i][w][3]!=INF)
             {
              //    getchar();
               dp[i+1][w+1][0]=min(dp[i][w][3]+2,dp[i+1][w+1][0]);
            //    printf("! %d %d %d\n", dp[i+1][w+1][0],i+1,w+1);
               dp[i+1][w+2][1]=min(dp[i][w][3]+2,dp[i+1][w+2][1]);
             //   printf("! %d %d %d\n",dp[i+1][w+2][1],i+1,w+2);
               if(td[i+1].ud==1)
               {
                 dp[i+1][w+1][2]=min(dp[i][w][3]+1,dp[i+1][w+1][2]);
                 dp[i+1][w+1][1]=min(dp[i+1][w+1][1],dp[i][w][3]+(td[i+1].n-td[i].n)+1);
               }
                if(td[i+1].ud==2)
                {
                 dp[i+1][w][3]=min(dp[i+1][w][3],dp[i][w][3]+(td[i+1].n-td[i].n));
              //    printf("! %d %d %d\n",dp[i+1][w][3],i+1,w);
                 dp[i+1][w+1][3]=min(dp[i][w][3]+1,dp[i+1][w+1][3]);
                }
              if(td[i+1].ud==3)
                 dp[i+1][w+1][1]=min(dp[i+1][w+1][1],dp[i][w][3]+(td[i+1].n-td[i].n)+1);
             }
            }
        int minn=INF;
        for(i=0;i<=3;i++)
          minn=min(minn,dp[tb][k][i]);
        printf("%d\n",minn);
     }
     return 0;
}

原来DP可以写这么多，，

回复：5楼
这哪算多。。