HDU 4804 Campus Design 轮廓线DP

本文主要是介绍HDU 4804 Campus Design 轮廓线DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4804

分情况讨论：
1.枚举的点上有障碍物，那么上一个阶段的状态，在这个点上面的格子一定有被填充
2.枚举的点上没有障碍物
a.这个格子不放，那么上一个阶段的状态上，这个点上面的格子一定有被填充
b.这个格子放1 * 1的物体，那么上一个阶段的状态，这个格子的上面也是被填充
c.这个格子横着放1 * 2，和一般的轮廓线DP一样
d.这个格子竖着放1 * 2 ,和一般的轮廓线DP一样

dp[cur][cnt][st] 表示在cur的阶段，我们用了cnt个1 * 1的格子，轮廓线状态是st的方案数

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1000000000 + 7;
const int maxn = 100 + 5,maxm = 10 + 5,maxst = 1 << 11,maxcnt = 20 + 1;
LL dp[2][maxcnt][maxst];
int mp[maxn][maxm];
int main(){int n,m,c,d;while(scanf("%d %d %d %d",&n,&m,&c,&d) != EOF){for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j) scanf("%1d",&mp[i][j]);memset(dp,0,sizeof dp);int cur = 0,max_st = 1 << m;dp[cur][0][max_st - 1] = 1;for(int i = 1;i <= n;++i){for(int j = 1;j <= m;++j){cur = 1 - cur;memset(dp[cur],0,sizeof dp[cur]);for(int st = 0;st < max_st;++st){       //枚举上一个阶段的状态for(int cnt = 0;cnt <= d;++cnt){    //枚举上一个阶段的1 * 1个数if(mp[i][j] == 0){              //如果当前位置有障碍物if((st & (1 << m - 1))) dp[cur][cnt][(st << 1) ^ (1 << m) ^ 1] += dp[1 - cur][cnt][st],dp[cur][cnt][(st << 1) ^ (1 << m) ^ 1] %= mod;}else{                           //如果当前位置没有障碍物//当前位置放1 * 1if(cnt + 1 <= d && (st & (1 << m - 1))) dp[cur][cnt + 1][(st << 1) ^ (1 << m) ^ 1] += dp[1 - cur][cnt][st],dp[cur][cnt + 1][(st << 1) ^ (1 << m) ^ 1] %= mod;//当前位置不放if((st & (1 << m - 1))) dp[cur][cnt][(st << 1) ^ (1 << m)] += dp[1 - cur][cnt][st],dp[cur][cnt][(st << 1) ^ (1 << m)] %= mod;//当前位置竖着放1 * 2if(i != 1 && !(st & (1 << m - 1))) dp[cur][cnt][(st << 1) ^ 1] += dp[1 - cur][cnt][st],dp[cur][cnt][(st << 1) ^ 1] %= mod;//当前位置横着放1 * 2if(j != 1 && (st & (1 << m - 1)) && !(st & 1)) dp[cur][cnt][(st << 1) ^ (1 << m) ^ 3] += dp[1 - cur][cnt][st],dp[cur][cnt][(st << 1) ^ (1 << m) ^ 3] %= mod;}}}}}LL ret = 0;for(int cnt = c;cnt <= d;++cnt) ret += dp[cur][cnt][max_st - 1],ret = ret % mod;printf("%lld\n",ret);}
}