题解：AT_judge_update_202004_c Numbering Blocks

Warning

这篇文章是 C++ 的福利，P 党请跳过。

看到题目，嗯……这题怎么做呢？应该是

\mathcal{O}(n^3)

的 dp 吧，让我们看看数据范围：What！

N \le 9

！~~STL 启动！~~

next_permutation 大法好！

直接枚举每个填数字的方法然后再判断是否合法就可以了。

时间复杂度：

\mathcal{O}(N\times N!)

，轻松通过。

Code

CPP

#include <bits/stdc++.h>

using namespace std;

long long a1, a2, a3, Ans, a[100];

bool pd(){
	for(int i = 1; i <= a1; ++ i){
		if(a[i] <= a[i - 1]) return false;
	}
	
	for(int i = a1 + 1; i <= a1 + a2; ++ i){
		if(a[i] <= a[i - 1]) return false;
		if(a[i] <= a[i - a1]) return false;
	}
	
	for(int i = a1 + a2 + 1; i <= a1 + a2 + a3; ++ i){
		if(a[i] <= a[i - 1]) return false;
		if(a[i] <= a[i - a1 - a2]) return false;
	}
	
	return true;
}

int main(){
	cin >> a1 >> a2 >> a3;
	
	for(int i = 1; i <= a1 + a2 + a3; ++ i){
		a[i] = i;
	}
	
	do{
		if(pd()){
			Ans ++;
		}
	}while(next_permutation(a + 1, a + a1 + a2 + a3 + 1));
	
	cout << Ans;
}

题解：AT_judge_update_202004_c Numbering Blocks

文章操作

相关推荐

评论

题解：AT_judge_update_202004_c Numbering Blocks