题意：

思路：

先预处理出所有格子的statement

statement=1–>只有上边的格子被覆盖

statement=2–>只有下边的格子被覆盖

statement=3–>上下都被覆盖

f[i][j][k]表示状态为i时，前j个地方的奶牛,盖k座房子 最少盖住的格子

i有四种情况

• i=1代表只有上边的格子被覆盖
• i=2代表只有下边的格子被覆盖
• i=3代表上下被同一个房子覆盖

• i=4代表上下被不同房子覆盖

  状态转移很麻烦 特别麻烦

• statement=1时

f[1][j][k]=min(min(f[1][j-1][k-1],min(f[2][j-1][k-1],min(f[3][j-1][k-1],f[4][j-1][k-1])))+1,f[1][j-1][k]+node[j].pos-node[j-1].pos);

f[1][j][k]=min(f[1][j][k],f[4][j-1][k]+node[j].pos-node[j-1].pos);

f[3][j][k]=min(temp+2,f[3][j-1][k]+2*(node[j].pos-node[j-1].pos));

f[4][j][k]=f[4][j-1][k]+2*(node[j].pos-node[j-1].pos);

f[4][j][k]=min(f[4][j][k],f[1][j-1][k-1]+node[j].pos-node[j-1].pos+1);

f[4][j][k]=min(f[4][j][k],f[2][j-1][k-1]+node[j].pos-node[j-1].pos+1);

• statement=2时同理
• statement=3时

int temp=min(f[1][j-1][k-1],min(f[2][j-1][k-1],min(f[3][j-1][k-1],f[4][j-1][k-1])));

f[3][j][k]=min(temp+2,f[3][j-1][k]+2*(node[j].pos-node[j-1].pos));

if(k>1)f[4][j][k]=min(f[1][j-1][k-2],min(f[2][j-1][k-2],min(f[3][j-1][k-2],f[4][j-1][k-2])))+2;

f[4][j][k]=min(f[4][j][k],f[4][j-1][k]+2*(node[j].pos-node[j-1].pos));

f[4][j][k]=min(f[4][j][k],f[1][j-1][k-1]+node[j].pos-node[j-1].pos+1);

f[4][j][k]=min(f[4][j][k],f[2][j-1][k-1]+node[j].pos-node[j-1].pos+1);

最后代码如下：

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;int n,K,b,cnt,f[5][1005][1005];struct Node{
    int sta,pos;}node[1005];bool cmp(Node a,Node b){    return a.pos
        
         1)f[4][j][k]=min(f[1][j-1][k-2],min(f[2][j-1][k-2],min(f[3][j-1][k-2],f[4][j-1][k-2])))+2;                    f[4][j][k]=min(f[4][j][k],f[4][j-1][k]+2*(node[j].pos-node[j-1].pos));                    f[4][j][k]=min(f[4][j][k],f[1][j-1][k-1]+node[j].pos-node[j-1].pos+1);                    f[4][j][k]=min(f[4][j][k],f[2][j-1][k-1]+node[j].pos-node[j-1].pos+1);                }            }        }    }    for(int i=1;i<=4;i++)f[1][cnt][K]=min(f[1][cnt][K],f[i][cnt][K]);    printf("%d\n",f[1][cnt][K]);}