poj 2430 Lazy Cows 状压dp

这个题目还是比较容易想到用状态dp来解的，但是状态的转移比较麻烦，并且加上有离散化，比较容易出错。

dp[i][j][k]表示覆盖前i列，用了j个矩形，当前覆盖状态为k的最优解。

k==1：覆盖1号格子

k==2：覆盖2号格子

k==3：覆盖1，2号格子，并且为同一个矩形

k==4：覆盖1，2号格子，并且为不同矩形

那么转移的时候就需要考虑，新建矩形，或者直接把当前矩形边长延伸。转移种类较多。

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
const int maxn=1e3+9;  
bool a[3][maxn];  
int x[maxn],y[maxn],f[maxn],g[maxn];  
int dp[maxn][maxn][5];  
struct D  
{  
    int id,key;  
    bool operator <(const D & xx) const  
    {  
        return key<xx.key;  
    }  
}h[maxn];  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    int n,K,b;  
    while(scanf("%d %d %d",&n,&K,&b)!=EOF)  
    {  
        memset(a,0,sizeof(a));  
        for(int i=1;i<=n;i++)  
        {  
            scanf("%d %d",&x[i],&y[i]);  
            h[i].key=y[i],h[i].id=i;  
        }  
        sort(h+1,h+1+n);  
        int top=0;  
        f[h[1].id]=++top;  
        g[top]=h[1].key;  
        for(int i=2;i<=n;i++)  
        {  
            if(h[i].key!=h[i-1].key) ++top;  
            f[h[i].id]=top;  
            g[top]=h[i].key;  
        }  
        for(int i=1;i<=n;i++)  
        a[x[i]][f[i]]=1;  
  
        memset(dp,50,sizeof(dp));  
        dp[0][0][0]=0;  
        for(int k=0;k<top;k++)  
        {  
            for(int i=0;i<=K;i++)  
            for(int j=0;j<5;j++)  
            {  
                if(a[1][k+1]==0)  
                dp[k+1][i+1][2]=min(dp[k+1][i+1][2],dp[k][i][j]+1);  
  
                if(a[2][k+1]==0)  
                dp[k+1][i+1][1]=min(dp[k+1][i+1][1],dp[k][i][j]+1);  
  
                dp[k+1][i+1][3]=min(dp[k+1][i+1][3],dp[k][i][j]+2);  
                dp[k+1][i+2][4]=min(dp[k+1][i+2][4],dp[k][i][j]+2);  
  
                if(j==1)  
                {  
                    if(a[2][k+1]==0)  
                    dp[k+1][i][j]=min(dp[k+1][i][j],dp[k][i][j]+g[k+1]-g[k]);  
                    else  
                    dp[k+1][i+1][4]=min(dp[k+1][i+1][4],dp[k][i][j]+g[k+1]-g[k]+1);  
                }  
                else if(j==2)  
                {  
                    if(a[1][k+1]==0)  
                    dp[k+1][i][j]=min(dp[k+1][i][j],dp[k][i][j]+g[k+1]-g[k]);  
                    else  
                    dp[k+1][i+1][4]=min(dp[k+1][i+1][4],dp[k][i][j]+g[k+1]-g[k]+1);  
                }  
                else if(j==3)  
                {  
                    dp[k+1][i][j]=min(dp[k+1][i][j],dp[k][i][j]+(g[k+1]-g[k])*2);  
                }  
                else if(j==4)  
                {  
                    dp[k+1][i][j]=min(dp[k+1][i][j],dp[k][i][j]+(g[k+1]-g[k])*2);  
  
                    if(a[2][k+1]==0)  
                    dp[k+1][i][1]=min(dp[k+1][i][1],dp[k][i][j]+g[k+1]-g[k]);  
                    else  
                    dp[k+1][i+1][4]=min(dp[k+1][i+1][4],dp[k][i][j]+g[k+1]-g[k]+1);  
  
                    if(a[1][k+1]==0)  
                    dp[k+1][i][2]=min(dp[k+1][i][2],dp[k][i][j]+g[k+1]-g[k]);  
                    else  
                    dp[k+1][i+1][4]=min(dp[k+1][i+1][4],dp[k][i][j]+g[k+1]-g[k]+1);  
                }  
            }  
        }  
  
        int ans=1e9;  
  
        for(int k=0;k<=K;k++)  
        for(int i=0;i<5;i++)  
        ans=min(ans,dp[top][k][i]+K-k);  
        cout<<ans<<endl;  
    }  
    return 0;  
}

补充：软件开发 , C++ ,