C++實現(xiàn)藍橋杯競賽題目---搭積木

更新時間：2021年07月06日 15:09:15 作者：一只特立獨行的貓

這篇文章主要介紹了C++實現(xiàn)藍橋杯競賽題目---搭積木,本篇文章通過題目分析列舉公式進行分析算法,包含詳細的圖文,以下就是詳細內容,需要的朋友可以參考下

小明對搭積木非常感興趣。他的積木都是同樣大小的正立方體。
在搭積木時，小明選取 m 塊積木作為地基，將他們在桌子上一字排開，中間不留空隙，并稱其為第0層。
隨后，小明可以在上面擺放第1層，第2層，……，最多擺放至第n層。擺放積木必須遵循三條規(guī)則

規(guī)則1：每塊積木必須緊挨著放置在某一塊積木的正上方，與其下一層的積木對齊；

規(guī)則2：同一層中的積木必須連續(xù)擺放，中間不能留有空隙；

規(guī)則3：小明不喜歡的位置不能放置積木。

其中，小明不喜歡的位置都被標在了圖紙上。圖紙共有n行，從下至上的每一行分別對應積木的第1層至第n層。每一行都有m個字符，字符可能是‘.'或‘X'，其中‘X'表示這個位置是小明不喜歡的。
現(xiàn)在，小明想要知道，共有多少種放置積木的方案。他找到了參加藍橋杯的你來幫他計算這個答案。
由于這個答案可能很大，你只需要回答這個答案對1000000007(十億零七)取模后的結果。
注意：地基上什么都不放，也算作是方案之一種。

輸入格式：
數(shù)據(jù)的第一行有兩個正整數(shù)n和m，表示圖紙的大小。
隨后n行，每行有m個字符，用來描述圖紙。每個字符只可能是‘.'或‘X'。

輸出格式：
一個整數(shù)，表示答案對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長度放置積木的可能數(shù)=在i-1層的所有包含a到b的長度的積木的可能數(shù)的和。

除了單純的判斷遞推式以外，還需要考慮一種特殊情況，就是積木放置的長度中存在X，即小明不想放的位置，那么就不需要進行遞推，直接返回0。
判斷[a,b]是否存在X，可以用前綴和來判斷，節(jié)省時間。
前綴和初始化為：

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區(qū)間存在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];//記錄數(shù)量
			}
		}
	}
	cout << cnt;
	return 0;
}

優(yōu)化

但是仔細一想，五個for循環(huán)無法通過最后50%的測試點，所以需要進行優(yōu)化，觀察最內層的兩個c，d的for循環(huán)可知，有如下圖像：

在這里插入圖片描述

實際上最內層的兩個循環(huán)就是在求第i-1層的紅色區(qū)域面積。
那我們再利用二維的前綴和進行存儲，那就可以優(yōu)化掉兩個循環(huán)，從而使時間復雜度降低，通過最后的測試點。

#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層的前綴和數(shù)組
	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++) {//層數(shù)
		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區(qū)間存在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;//防止出現(xiàn)負數(shù)
	return 0;
}

到此這篇關于C++實現(xiàn)藍橋杯競賽題目---搭積木的文章就介紹到這了,更多相關C++實現(xiàn)藍橋杯---搭積木內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: