HDU 4804 캠퍼스 디자인 윤곽선 dp

위의 윤곽선 dp 와 같 지만 두 가지 조건 이 더 많아 졌 습 니 다. 하 나 는 원 그림 에 놓 을 수 없 는 (즉 장애) 가 있 을 수 있 기 때문에 옮 길 때 color [i] [j] 가 1 과 같은 지 아 닌 지 를 판단 해 야 합 니 다. 다른 하 나 는 우리 가 더 많은 1 * 1 의 골 패 를 사용 할 수 있 습 니 다. 1 * 1 의 골 패 는 반드시 [c, d] 사이 에 있어 야 하기 때문에 상태 가 1 차원 을 더 해 야 합 니 다.옮 길 때 한 가지 상황 이 더 많다.그럼 어떻게 초기 화 할 까요?두 가지 방법 이 있 는데 하 나 는 dp [0] [0] [d] = 1 이다. 마지막 답 은 반드시 [c, d] 사 이 를 써 야 하기 때문에 정 답 은 dp [(t + 1) & 1] [0] [0 ~ d - c] 이다. 다른 하 나 는 dp [0] [0] [c ~ d] = 1 이 고 마지막 답 은 dp [(t + 1) & 1] [0] [0] [0] [0] 이다.
배우 면 간단 하 다 고 생각 합 니 다. 60 줄 이 안 되 는 코드 가 은상 과 의 만 남 을 놓 쳐 가슴 이 아 픕 니 다 ~
밑 에 코드 한 발 ~

#pragma warning(disable:4996)

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<vector>

#include<cmath>

#include<cstdio>

#define mod 1000000007

#define maxn 100

#define maxm 10

using namespace std;



char color[maxn + 50][maxm + 5];

int dp[2][1 << (maxm+1)][25];

int n, m, c, d;



int main()

{

	while (~scanf("%d%d%d%d", &n, &m, &c, &d))

	{

		for (int i = 0; i < n; i++) scanf("%s", color[i]);

		memset(dp, 0, sizeof(dp));

		dp[0][0][d] = 1;

		int t = 0;

		for (int i = 0; i < n; i++){

			for (int j = 0; j < m; j++){

				t = i*m + j;

				memset(dp[(t + 1) & 1], 0, sizeof(dp[(t + 1) & 1]));

				for (int k = 0; k < 1 << m; k++){

					for (int r = 0; r <= d; r++){

						if ((k >> j) & 1 || color[i][j] == '0'){

							dp[(t + 1) & 1][k&~(1 << j)][r] = (dp[t & 1][k][r] + dp[(t + 1) & 1][k&~(1 << j)][r]) % mod;

						}

						else{

							if (j + 1 < m && color[i][j + 1] == '1'&& !(k >> (j + 1) & 1)){

								dp[(t + 1) & 1][k | (1 << (j + 1))][r] = (dp[t & 1][k][r] + dp[(t + 1) & 1][k | (1 << (j + 1))][r]) % mod;

							}

							if (i + 1 < n&&color[i + 1][j] == '1'){

								dp[(t + 1) & 1][k | (1 << j)][r] = (dp[t & 1][k][r] + dp[(t + 1) & 1][k | (1 << j)][r]) % mod;

							}

							if (r > 0){

								dp[(t + 1) & 1][k][r - 1] = (dp[t & 1][k][r] + dp[(t + 1) & 1][k][r - 1]) % mod;

							}

						}

					}

				}

			}

		}

		int ans = 0;

		for (int i = d - c; i >= 0; i--){

			ans = (ans + dp[(t + 1) & 1][0][i]) % mod;

		}

		printf("%d
", ans);

	}

	return 0;

}