Vijos 1350 C数列

www.vijos.cn/Problem_Show.asp
话说Vijos的很多题目都有点问题,这个明显有多解的但连解的要求的没有说囧。。
这是经典剪枝问题了。。我欺负题的数据比较小,随便写了几个剪枝就过了(*^__^*)
首先是所有数一定要递增,如果不递增的话更改操作顺序是可以改成递增的,那就没必要重复搜索了。替代性剪枝
其次如果当前最大数超过需要的数了,最优性剪枝。
使用DFSID,如果还能迭代d次,当前最大数*2^d次方小于n,可行性剪枝。
同时搜索的时候从后往前搜数,更快逼近答案。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100;
int n;
int A[maxn];
bool dfs(int p,int d)
{
if(!d)return false;
if(A[p-1]>n||(A[p-1]<<d)<n)return false;
if(A[p-1]==n)return true;
for(int i=p-1;i>=0;–i)
for(int j=i;j>=0;–j)
{
int x=A[i]+A[j];
if(x<=A[p-1])break;
A[p]=x;
if(dfs(p+1,d-1))return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
cin>>n;A[0]=1;
for(int i=1;;i++)
if(dfs(1,i))
{
cout<<i<<endl;
rep(j,i)cout<<A[j]<<" ";
cout<<endl;
break;
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>