目录

L2-4-吉利矩阵

L2-4 吉利矩阵

https://i-blog.csdnimg.cn/direct/8867fce72c5f48fd8d6b148311088a53.png

输入样例:

7 3

输出样例:

666

这道题是暴力纯搜,但是很难想,我这个是看的别人的代码

#include "bits/stdc++.h"
using namespace std;
int x[20][20];
int l, n;
int cnt = 0;
int sumx[5], sumy[5];
void dfs(int x, int y){
	if(x == n + 1) {
		cnt ++;
		return;
	}
//	其实不需要考虑列的和是否满足l ,因为如果超出l的话 根本不会进入循环,如果列不足l的话,行也不可能在某一行没有超出l的情况下一整行都达到l,所以两个约束条件限制了sumy一定是合理的 
	for(int i = 0; i <= min(l - sumx[x], l - sumy[y]);i ++){ //控制剩下的元素的取值范围 
		sumx[x] += i; //第x行的元素的和 
		sumy[y] += i; //第y列的元素的和 
		if(y < n) dfs(x, y +1);
		else if(y == n && sumx[x] == l) dfs(x + 1, 1);
		sumx[x] -= i;
		sumy[y] -= i;
	}
}
int main(){
	int a, b;
	cin>>l>>n;
	dfs(1, 1);
	cout<<cnt<<endl;
//	cout<<ans<<endl;
	return 0;
}