C++實(shí)現(xiàn)藍(lán)橋杯競(jìng)賽題目---搭積木

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

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

小明對(duì)搭積木非常感興趣。他的積木都是同樣大小的正立方體。
在搭積木時(shí)，小明選取 m 塊積木作為地基，將他們?cè)谧雷由弦蛔峙砰_(kāi)，中間不留空隙，并稱(chēng)其為第0層。
隨后，小明可以在上面擺放第1層，第2層，……，最多擺放至第n層。擺放積木必須遵循三條規(guī)則

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

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

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

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

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

輸出格式：
一個(gè)整數(shù)，表示答案對(duì)1000000007取模后的結(jié)果。

輸入樣例1：

2 3

..X

.X.

輸出樣例1：

4

輸入樣例2：

3 3

..X

.X.

...

輸出樣例2：

16

解題思路：

在這里插入圖片描述

首先先推導(dǎo)出遞推式，觀察題目，可以得到遞推式為：

在這里插入圖片描述

用代碼表示即為：

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長(zhǎng)度放置積木的可能數(shù)=在i-1層的所有包含a到b的長(zhǎng)度的積木的可能數(shù)的和。

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

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

推導(dǎo)出遞推式以后可以很容易的寫(xiě)出代碼：

#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層，長(zhǎng)度從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)化

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

在這里插入圖片描述

實(shí)際上最內(nèi)層的兩個(gè)循環(huán)就是在求第i-1層的紅色區(qū)域面積。
那我們?cè)倮枚S的前綴和進(jìn)行存儲(chǔ)，那就可以?xún)?yōu)化掉兩個(gè)循環(huán)，從而使時(shí)間復(fù)雜度降低，通過(guò)最后的測(cè)試點(diǎ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];//用來(lái)判斷是否存在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層，長(zhǎng)度從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)負(fù)數(shù)
	return 0;
}

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

您可能感興趣的文章: