C++블 루 브리지 컵 경기 제목 실현-블록 쌓 기

샤 오 밍 은 블록 쌓 기 에 매우 흥 미 를 느낀다.그의 블록 은 모두 같은 크기 의 정사각형 이다.
블록 을 쌓 을 때 샤 오 밍 은 m 개의 블록 을 토대 로 그들 을 책상 위 에 일자 로 배열 하고 중간 에 공간 을 남기 지 않 으 며 0 층 이 라 고 부른다.
이 어 샤 오 밍 은 1 층,2 층,...................................................................적 목 을 놓 으 려 면 반드시 세 가지 규칙 을 따라 야 한다.
규칙 1:모든 블록 은 특정한 블록 의 바로 위 에 바짝 붙 어서 다음 층 의 블록 과 정렬 해 야 한다.
규칙 2:같은 층 에 쌓 인 나 무 는 반드시 연속 적 으로 배치 해 야 하 며 중간 에 틈 이 있어 서 는 안 된다.
규칙 3:샤 오 밍 이 싫어 하 는 위치 에 블록 을 놓 을 수 없다.
이 가운데 샤 오 밍 이 싫어 하 는 위치 가 모두 도면 에 표시 됐다.도면 은 모두 n 줄 로 아래 에서 위로 각 줄 이 각각 블록 의 1 층 에서 n 층 까지 대응 된다.줄 마다 m 개의 문자 가 있 는데 문 자 는''또는'X'일 수 있 습 니 다.그 중에서'X'는 이 위 치 를 샤 오 밍 이 좋아 하지 않 는 다 는 것 을 나타 냅 니 다.
이제 샤 오 밍 은 블록 을 놓 는 방안 이 얼마나 되 는 지 알 고 싶 어 한다.그 는 블 루 브리지 컵 에 참가 한 너 를 찾 아 이 답안 을 계산 해 주 었 다.
이 답 은 매우 클 수 있 기 때문에,너 는 이 답 이 1000000007(10 억 7 천만)을 모델 로 한 결과 에 만 대답 해 야 한다.
주의:지반 에 아무것도 놓 지 않 는 것 도 방안 의 하나 라 고 할 수 있 습 니 다.
입력 형식:
데이터 의 첫 줄 은 두 개의 정수 n 과 m 로 도면 의 크기 를 나타 낸다.
다음 n 줄,줄 마다 m 글자 가 있어 도면 을 설명 합 니 다.모든 문 자 는''또는'X'일 수 있 습 니 다.
출력 형식:
하나의 정 수 는 답 이 1000000007 을 모델 로 한 결 과 를 나타 낸다.
입력 샘플 1:
2 3
..X
.X.
출력 예시 1:
4
입력 샘플 2:
3 3
..X
.X.
...
출력 예시 2:
16
문제 풀이 방향:

먼저 전달 식 을 유도 하고 문 제 를 관찰 하면 전달 식 을 얻 을 수 있다.

코드 로 표시 하면:

for(int c=1;c<a;c++){
	for(int d=b;d<m;d++){
		dp[i][a][b]+=dp[i-1][c][d];
	}
}

뜻 은
i 층 의 a 에서 b 까지 의 길이 에 블록 을 설치 할 수 있 는 가능 수=i-1 층 의 모든 a 에서 b 까지 의 길 이 를 포함 하 는 블록 의 가능 수 와.
단순히 전달 식 을 판단 하 는 것 외 에 블록 이 놓 인 길이 에 X,즉 샤 오 밍 이 놓 고 싶 지 않 은 위치 가 있다 면 전달 하지 않 고 바로 0 으로 되 돌아 가 는 특수 한 상황 도 고려 해 야 한다.
[a,b]의 존재 여 부 를 판단 하려 면 접두사 와 판단 으로 시간 을 절약 할 수 있다.
접두사 와 초기 화:

s[i][j] = s[i][j-1] + (temp=='X');

전달 식 을 유도 한 후에 코드 를 쉽게 쓸 수 있 습 니 다.

#include<iostream>

using namespace std;

const int N = 30;
int n, m;
int dp[30][30][30];
int s[30][30];
int cnt=1;

int main() {
	cin >> n >> m;
	getchar();
	for (int i = n; i >0; i--) {//      
		for (int j = 1; j <= m; j++) {
			char temp = getchar();
			s[i][j] = s[i][j-1] + (temp=='X');
		}
		getchar();
	}
	dp[0][1][m]=1;// 0 ，   1 m        
	for (int i = 1; i <=n; i++) {// i 
		for (int a = 1; a <= m; a++) {
			for (int b = a; b <= m; b++) {
				if (s[i][b] - s[i][a - 1] != 0) {//a b    X
					dp[i][a][b] = 0;
					continue;
				}
				for (int c = 1; c <= a; c++) {
					for (int d = b; d <= m; d++) {
						dp[i][a][b] += dp[i - 1][c][d];
					}
				}
				cnt += dp[i][a][b];//    
			}
		}
	}
	cout << cnt;
	return 0;
}

최적화 하 다.
그러나 자세히 생각해 보면 다섯 개의 for 순환 은 마지막 50%의 테스트 점 을 통과 할 수 없 기 때문에 최 적 화 를 해 야 한다.가장 안쪽 에 있 는 두 개의 c,d 의 for 순환 을 관찰 하면 다음 과 같은 이미지 가 있다.

실제로 가장 안쪽 의 두 순환 은 i-1 층 의 빨간색 구역 면적 을 구 하 는 것 이다.
그러면 우 리 는 2 차원 접두사 와 저장 을 이용 하면 두 순환 을 최적화 시 켜 시간 복잡 도 를 낮 추고 마지막 테스트 점 을 통과 할 수 있다.

#include<iostream>

using namespace std;

const int N = 30;
const int mod = 1e9 + 7;
int n, m;
int dp[30][30][30];
int s[30][30];//        X
int sum[30][30];//        dp[i][][]  
int cnt=1;

void get_fixsum(int i) {
	//   i       
	for (int a = 1; a <= m; a++) {
		for (int b = 1; b <= m; b++) {
			sum[a][b] =(sum[a][b-1]+sum[a-1][b]-sum[a-1][b-1]+ dp[i][a][b])%mod;
		}
	}
}

int main() {
	cin >> n >> m;
	getchar();
	for (int i = n; i >0; i--) {
		for (int j = 1; j <= m; j++) {
			char temp = getchar();
			s[i][j] = s[i][j-1] + (temp=='X');
		}
		getchar();
	}
	dp[0][1][m]=1;// 0 ，   1 m        
	get_fixsum(0);
	for (int i = 1; i <=n; i++) {//  
		for (int a = 1; a <= m; a++) {
			for (int b = a; b <= m; b++) {
				if (s[i][b] - s[i][a - 1] != 0) {//a b    X
					dp[i][a][b] = 0;
					continue;
				}
				dp[i][a][b] = (sum[a][m] - sum[0][m] - sum[a][b-1] + sum[0][b-1])%mod;
				cnt =(cnt+ dp[i][a][b])%mod;
			}
		}
		get_fixsum(i);
	}
	cout << (cnt+mod)%mod;//      
	return 0;
}

여기 서 C++블 루 브리지 컵 경기 의 제목 인 블록 을 쌓 는 것 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C+블 루 브리지 컵 을 실현 합 니 다.블록 을 쌓 는 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 십시오.앞으로 우 리 를 많이 지지 해 주시 기 바 랍 니 다!