有这么一个游戏：
写出一个1～N的排列a[i]，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：
3 1 2 4
4 3 6
7 9
16
最后得到16这样一个数字。
现在想要倒着玩这样一个游戏，如果知道N，知道最后得到的数字的大小sum，请你求出最初序列a[i]，为1～N的一个排列。若答案有多种可能，则输出字典序最小的那一个。 (n<12)
首先我们通过手算及暴力程序应该可以发现
设 sum 为最后一行的值
总共有 1 行 则 sum=a1*1
总共有 2 行 则 sum=a1*1+a2*1
总共有 3 行 则 sum=a1*1+a2*2+a3*1
总共有 4 行 则 sum=a1*1+a2*3+a3*3+a4*1
不难发现sum等于二项式定理中的系数乘上第n个数
所以对于这题我们只需要先预处理出二项式定理的系数 再对1~n进行dfs排列 适当加上一个剪枝就能AC
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[13],n,m,sum,b[13],last_num[13];
bool k[13],p;
void dfs(long long now,long long num,long long now_num)//当前位置 到当前位置的总和 当前位置的数值
{
if(p)//取到解就不必再继续dfs
return ;
if(now==n)
{
if(num==m)
{
for(long long i=1;i<=n;i++)
printf("%lld ",a[i]);
p=1;
return ;
}
else
{
k[now_num]=0;
return ;
}
} for(long long i=1;i<=n;i++)
{
if(!k[i])
{
if(num+i*b[now+1]>m)//一个小剪枝 如果总和大于所要的解则不再扩展
{
k[now_num]=0;
return;
}
else
{
k[i]=1;
a[now+1]=i;
dfs(now+1,num+i*b[now+1],i);
k[i]=0;//根据函数定义的回溯法求排列
}
}
}
}
int main()
{
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++)
{
b[i]=1;
for(long long j=i-1;j>=1;j--)
b[j]+=b[j-1];
}
for(long long i=n;i>=1;i--)
{
last_num[i]=b[i]+last_num[i+1];
}
dfs(0,0,0);
}
n<12
对于原题中的n<12 我们的总和超过m就剪枝的做法是完全可以的
但教练提了一个n<20 的问题 这时一个剪枝就显得不足了（只能拿20分）
我们可以用IDA*的算法
即在dfs扩展时计算未来可能的代价 如果代价超出能忍受的范围则剪枝
我们考虑下面三个剪枝
剪枝一：
计算当前的“累加和”，若超出Sum，则没必要继续搜索
剪枝二：
计算当前的“累加和”+“未来的最小累加和”，若超出Sum，则没必要继续搜索
剪枝三：
计算当前的“累加和”+“未来的最大累加和”，若小于Sum，则没必要继续搜索
其中剪枝 二 三 就是对未来的一个估价函数
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[21],n,m,sum,b[21],sort_num[21],pai[21],minm,maxm;
bool k[21],p,c;
void yugu(long long now)
{
pai[0]=0;
sort_num[0]=0;
maxm=0;
minm=0;
for(long long i=n/2+1;i>=now;i--)
pai[++pai[0]]=b[i];
for(long long i=n/2+2;i<=n;i++)
pai[++pai[0]]=b[i];
for(long long i=1;i<=n;i++)
{
if(!k[i])
sort_num[++sort_num[0]]=i;
}
for(long long i=1;i<=sort_num[0];i++)
{
minm+=sort_num[i]*pai[i];
maxm+=sort_num[i]*pai[sort_num[0]-i+1];
}
}
void dfs(long long now,long long num)
{ if(c)
return ;
if(num>m)
return ;
yugu(now+1);//进行预估代价
if(num+maxm<m||num+minm>m)//判断是否可行剪枝
return ;
if(now==n)
{
if(num==m)
{
for(long long i=1;i<=n;i++)
printf("%lld ",a[i]);
c=1;
return ;
}
else
return ;
}
for(long long i=1;i<=n;i++)
{ if(!c)
if(!k[i])
{
if(num+i*b[now+1]>m)
continue;
else
{
k[i]=1;
a[now+1]=i;
dfs(now+1,num+i*b[now+1]);
k[i]=0;
}
}
}
}
int main()
{
// freopen("szyx.in","r",stdin);
// freopen("szyx.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++)
{
b[i]=1;
for(long long j=i-1;j>=1;j--)
b[j]+=b[j-1];
}
dfs(0,0);
return 0;
}
启发式搜索 IDA*
