poj 2430 Lazy Cows 状压dp - c++编程基础

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

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

k==1：覆盖1号格子

k==2：覆盖2号格子

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

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

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

#include   
#include   
#include   
#include   
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