【团体程序设计天梯赛】L2-052 吉利矩阵

本文主要是介绍【团体程序设计天梯赛】L2-052 吉利矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

直接回溯枚举每一个位置填的数，二维肯定是不方便的，我们转成一维，下标x从0到n*n-1。二维数组下标从0到n-1，在一维中下标为x的点在二维中对应行是x/n，列是x%n。

每个数最小能填的是0，最大肯定就是l了，时间复杂度的上限是n的2l次幂，4的18大概是1e11这样。

我们直接标记每行sum和每列sum，因为只有当前填的元素只会影响它所在的行和列，所以只要判断它所在行和列是否满足条件就行了。剪枝一下，具体的就是，当前和不能大于l，因为后面还有元素要加，以及，当前和加上后面元素的最大和能够大于等于l。

代码：

#include <iostream>
using namespace std;
int l,n,row[5],col[5],ans;void backtrack(int x){if(x==n*n){for(int i=0;i<n;i++){if(row[i]!=l) return;if(col[i]!=l) return;}ans++;return;}for(int i=0;i<=l;i++){//能填的数最小是0，最大是l//剪枝1：当前行或列值不超过lif(row[x/n]+i>l||col[x%n]+i>l) break;row[x/n]+=i;//对应行和更新col[x%n]+=i;//对应列和更新//剪枝2：加上其他没有填的数（取最大）能达到lif(row[x/n]+l*(n-1-x%n)>=l&&col[x%n]+l*(n-1-x/n)>=l)backtrack(x+1);row[x/n]-=i;//还原现场col[x%n]-=i;}
}
int main(){cin>>l>>n;backtrack(0);cout<<ans;return 0;
}

这篇关于【团体程序设计天梯赛】L2-052 吉利矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---