首页 > 代码库 > BZOJ 1653 [Usaco2006 Feb]Backward Digit Sums ——搜索
BZOJ 1653 [Usaco2006 Feb]Backward Digit Sums ——搜索
【题目分析】
劳逸结合好了。
杨辉三角+暴搜。
【代码】
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <map> #include <set> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define maxn 500005 #define inf 0x3f3f3f3f #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) void Finout() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif } int Getint() { int x=0,f=1; char ch=getchar(); while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,sum,a[15][15]; int list[15],hav[15]; bool dfs(int step,int s) { if (s>sum) return false; if (step==n+1&&s==sum) return true; if (step==n+1) return false; F(i,1,n) { if (!hav[i]) { list[step]=i; hav[i]=1; if (dfs(step+1,s+a[n][step]*i)) return true; hav[i]=0; } } return false; } int main() { Finout(); n=Getint(); sum=Getint(); F(i,1,12){a[i][1]=1;F(j,2,i)a[i][j]=a[i-1][j]+a[i-1][j-1];} // F(i,1,12) // { // F(j,1,i) // cout<<a[i][j]<<" "; // cout<<endl; // } if (dfs(1,0)) F(i,1,n-1) cout<<list[i]<<" "; cout<<list[n]<<endl; }
BZOJ 1653 [Usaco2006 Feb]Backward Digit Sums ——搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。