2018-1-30

直接用dfs求解即可，一開始的時候提交TLE，后來優化一下就OK了！

#include<iostream> #include<cstring> using namespace std;const int N = 10; int x[N+1],y[N+1],z[N+1]; bool f[N+1]; int n,s,sum;int cal(){int cnt=n;sum=0;for (int i=0;i<n;i++) z[i]=x[i];while (cnt!=1){for (int i=0;i<cnt-1;i++){int t=z[i]+z[i+1];z[i]=t;}cnt--;}sum=z[0];return sum; }void dfs(int step){if (step>n) return;if (step==n){cal();if (sum==s){for (int i=0;i<n;i++){y[i]=x[i];}}return;}for (int i=1;i<=n;i++){if (!f[i]){if (i>y[step]) return; //在這里進行優化，因為我們要保證得到的字典序是最小的，所以要求的不能大于已知的對應的那個值x[step]=i;f[i]=true;dfs(step+1);f[i]=false;}} }int main(){while (cin>>n>>s){memset(f,false,sizeof(f));memset(y,0x3f,sizeof(y));dfs(0);for (int i=0;i<n-1;i++){cout<<y[i]<<" ";}cout<<y[n-1]<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的poj3187 穷竭搜索 挑战程序设计大赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。