从左到右DP, 存储哪里有奶牛以后排序, 同一个x坐标的上下奶牛合并.. 0没有 1上 2下 3都有
随着奶牛的位置x从左到右DP, 需要记录的状态是dp[i][p][k], p是在x处的奶牛圈起来的方式, 我记的是 0没圈(这就初始状态可能) 1圈上 2圈下 3两个一起圈 4两个分开圈, 记录每个可能的k和对应的面积最小值
状态转移比较麻烦.. 我是又分两个状态之间的圈圈怎样互相结合来枚举,  0不结合 1上边延伸出去 2下边 3两边一起延伸 4两边分开延伸. 应该还有更巧妙的方法.. 不想再碰这题了
172ms 直接大数组20M内存..代码点下面

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int adoptable(int p,int q) {
    if(p==3||p==4)
        return q==p?0:-1;
    if(p==1||p==2) {
        if(q==p)
            return 0;
        if(q==4)
            return 1;
        return -1;
    }
    //p==0;
    return q==0?0:q==4?2:1;
}

int ifAddK(int p0,int p1,int stretch) {
    if(adoptable(stretch,p0)==-1)
        return -1;
    return adoptable(stretch,p1);
}

int cmp(const void *_a, const void *_b) {
    int a=*(int *)_a,b=*(int *)_b;
    return (a>>3)-(b>>3);
}

int main() {
    int N,K,B;
    scanf("%d%d%d",&N,&K,&B);

    int map[1001];
    for(int i=1;i<=N;i++)
        map[i]=-1;
    int mapN=0;
    for(int i=1;i<=N;i++) {
        int u,pos;
        scanf("%d%d",&u,&pos);
        int j;
        for(j=1;j<=mapN;j++)
            if( (map[j]>>3)==pos )
                break;
        if(j>mapN) {
            map[j]= (pos<<3)|u;
            mapN++;
        }
        else
            map[j]|=u;
    }

    qsort(map+1,mapN,sizeof(int),cmp);

    int (*dp)[5][1001];
    dp=(int (*)[5][1001])malloc(sizeof(int)*1001*5*1001);
    memset(dp[0],0xff,sizeof(dp[0]));
    dp[0][0][0]=0;
    map[0]=0;
    for(int i=1;i<=mapN;i++) {
        memset(dp[i],0xff,sizeof(dp[0]));

        for(int p0=0;p0<=4;p0++)    //Statu of last
            for(int p1=0;p1<=4;p1++)  // This state
            {
                if(p1!=4 && (p1|(map[i]&3))!=p1)
                    continue;
                for(int stretch=0;stretch<=4;stretch++) //which side stretching
                {
                    int addK=ifAddK(p0,p1,stretch);
                    if(addK==-1)
                        continue;

                    int addC=(map[i]>>3)-(map[i-1]>>3)-1;
                    addC*=(stretch==1||stretch==2)?1:stretch==0?0:2;
                    addC+=(p1==0)?0:(p1==1||p1==2)?1:2;
                    for(int k=0;k<=K;k++) {
                        int k1=k+addK;
                        if(k1>K)
                            break;
                        if(dp[i-1][p0][k]==-1)
                            continue;
                        if(dp[i][p1][k1]==-1||dp[i][p1][k1]>dp[i-1][p0][k]+addC)
                            dp[i][p1][k1]=dp[i-1][p0][k]+addC;
                    }
                }
            }
    }
    int result=2e9;
    for(int p=0;p<=4;p++)
        result=dp[mapN][p][K]!=-1&&dp[mapN][p][K]<result?dp[mapN][p][K]:result;
    printf("%d\n",result);
    return 0;
}