L2-4 吉利矩阵
输入样例:
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;
}