这道题的剪枝应该可以作为搜索中剪枝学习的一个典型案例，做完这题，深刻的感受到了剪枝的玄学
题目大意：给出一个N进制的加法算式（N最大为26），在这个加法算式中，数字都用大写字母表示，相同的数字用相同的字母表示，且给出的几个数中包含了表示0-N的所有字母。需要求解的是A-N表示的数字是多少。
剪枝思路
这个平台在提交的时候，一共有10个测试样例，每个10分，然后就开始了艰难的AC之旅
初始思路
由于测试样例给出的是A-E的五进制计算，所以，一下子想到的是根据A-E来进行搜索，也就是计算出A-E中的各个全排列方式，对于每一个全排列的方式，判断是否满足这个式子，如果满足，这输出该排列。
然后就有了如下代码
#include <iostream>
using namespace std;
int n,dp[26];
bool book[26],flag = 0;
char ch1[26],ch2[26],ch3[26];
int check() {
int weight = 0,ff = 1;
for (int i=n-1; i>=0; i--) {
int sum = dp[ch1[i]-'A'] + dp[ch2[i]-'A'] + weight;
weight = sum/n;
sum = sum % n;
if (dp[ch3[i]-'A']!=sum){
ff = 0;
break;
}
}
return ff;
}
void dfs(int step) {
if (flag) return;
if (step==n) {
if (check()) {
flag = 1;
for(int i=0; i<n; i++) cout<<dp[i]<<" ";
}
return ;
}
for (int i=n-1; i>=0; i--) {
if (!book[i]) {
book[i] = 1;
dp[step] = i;
dfs(step+1);
book[i] = 0;
}
}
}
int main(){
cin>>n;
for (int i=0; i<n; i++) cin>>ch1[I];
for (int i=0; i<n; i++) cin>>ch2[I];
for (int i=0; i<n; i++) cin>>ch3[I];
dfs(0);
return 0;
}
然后30分。也就是说只能过N<10的测试样例。
想想也是，26位的全排列，肯定是炸的，然后开始剪枝优化
剪枝优化
既然直接给出A-E的全排列再去判断会超时，那为什么不边给出全排列边判断呢。比如给出的ABCED+BDACE=EBBAA。那么就可以得到(D+E)%5=A，在进行全排列的过程中，如果不满足这个条件，就不需要再继续搜索下去了。
既然要边排列边判断，那肯定不能进行A-E的依次搜索。按照上面的思路，我们要先给DEA赋值，然后判断此值满不满足，如果满足，再给左边这一列ECA赋值。对于前面已经赋值过得字母，可以不用进行搜索，直接dfs(step+1)即可
具体实现就是，把给出的3段字母串，串成一串长串（最多78位），如上A-E所示的例子中，第一个ABCED所在的下标分别为：0,3,6,9,12
这样的赋值就可以吧这个长串作为搜索对象，直接进行搜索，在搜索的过程中，每搜索层数+3，就进行一次判断。
于是就有了如下代码：
#include <iostream>
#include <string.h>
using namespace std;
int n,book[26],all[78],dp[26],flag = 0;
char ch];
int check(int step) {
int weight = 0;
for (int i=0; i<step; i+=3) {
int sum = dp[all[i]] + dp[all[i+1]] + weight;
weight = 0;
if (sum>=n) weight = 1;
sum = sum % n;
if (dp[all[i+2]]!=sum) return 0;
}
return 1;
}
void dfs(int step) {
if (flag) return;
if (step%3==0&&!check(step)) return;
if (step==3*n) {
for (int i=0; i<n; i++) cout<<dp[i]<<" ";
flag = 1;
return;
}
if (dp[all[step]]==-1) {
for (int i=n-1; i>=0; i--) {
if (!book[i]) {
book[i] = 1;
dp[all[step]] = I;
dfs(step+1);
book[i] = 0;
dp[all[step]] = -1;
}
}
} else dfs(step+1);
}
int main(){
cin>>n;
memset(dp,-1,sizeof(dp));
for (int i=0; i<n; i++) {
cin>>ch;
all[3*(n-1-i)] = ch - 'A';
}
for (int i=0; i<n; i++) {
cin>>ch;
all[3*(n-1-i)+1] = ch - 'A';
}
for (int i=0; i<n; i++) {
cin>>ch;
all[3*(n-1-i)+2] = ch - 'A';
}
dfs(0);
return 0;
}
注意上面有一行。if (dp[all[step]]==-1) {，这是用来判断这个字母是否已经被赋值，如果被赋值就直接进入下一层的搜索即可，但是一定要加else
这个代码。90分
WTF，优化也优化了，剪枝也剪枝了，你还要我怎样。。
无奈的看了大神的思路之后。。。我表示真的没话讲，玄学剪枝
AC代码
#include <iostream>
#include <string.h>
using namespace std;
int n,book[26],all[78],dp[26],flag = 0;
char ch;
int check(int step) {
int weight = 0;
for (int i=0; i<step; i+=3) {
int sum = dp[all[i]] + dp[all[i+1]] + weight;
weight = 0;
if (sum>=n) weight = 1;
sum = sum % n;
if (dp[all[i+2]]!=sum) return 0;
}
return 1;
}
int checkFront(int step) {
for (int i=3*n-1; i>step; i-=3)
if (dp[all[i-2]]>=0&&dp[all[i-1]]>=0&&dp[all[i]]>=0&&dp[all[i]]!=(dp[all[i-1]]+dp[all[i-2]])%n&&dp[all[i]]!=(dp[all[i-1]]+dp[all[i-2]]+1)%n)
return 0;
return 1;
}
void dfs(int step) {
if (flag||!checkFront(step-1)) return;
if (step%3==0&&!check(step)) return;
if (step==3*n) {
for (int i=0; i<n; i++) cout<<dp[i]<<" ";
flag = 1;
return;
}
if (dp[all[step]]==-1) {
for (int i=n-1; i>=0; i--)
if (!book[i]) {
book[i] = 1;
dp[all[step]] = I;
dfs(step+1);
book[i] = 0;
dp[all[step]] = -1;
}
}
else dfs(step+1);
}
int main(){
cin>>n;
memset(dp,-1,sizeof(dp));
for (int i=0; i<n; i++) {
cin>>ch;
all[3*(n-1-i)] = ch - 'A';
}
for (int i=0; i<n; i++) {
cin>>ch;
all[3*(n-1-i)+1] = ch - 'A';
}
for (int i=0; i<n; i++) {
cin>>ch;
all[3*(n-1-i)+2] = ch - 'A';
}
dfs(0);
return 0;
}
玄学代码
int checkFront(int step) {
for (int i=3*n-1; i>step; i-=3)
if (dp[all[i-2]]>=0&&dp[all[i-1]]>=0&&dp[all[i]]>=0&&dp[all[i]]!=(dp[all[i-1]]+dp[all[i-2]])%n&&dp[all[i]]!=(dp[all[i-1]]+dp[all[i-2]]+1)%n)
return 0;
return 1;
}
上面的这个AC代码是在刚才90分代码的基础上，增加了这一段玄学剪枝。
具体是什么意思呢？就是，我们在进行判断的时候，从右往左进行了判断。也就是说，给DEA赋值之后，从右往左判断了(D+E)%5=A是否成立。但是，这个玄学的剪枝还要加一个从左往右！
也就是说，就算这个式子右边是DEA，其中D=4、E=2、A=1。是不是没毛病，是不是要继续搜索下去。但是如果这个式子左边是DAE，即要判断(D+A)%5=E，从右往左计算时，要考虑进位，所以只要满足(D+A)%5=E或(D+A+1)%5=E两者之一即可。但是你会发现，这两者都不满足！
也就是说，这个DEA的赋值情况，在右侧满足了条件，但是在左侧不满足，那这个搜索也不需要进行下去，因为它迟早会进行到左边，到达那个不满足的点！
对于这道题，没啥多说的，活到老学到老以及无奈的微笑:)
网友评论