題目連接：

http://codeforces.com/gym/101473/attachments

原先以為按照這個復雜度還要剪一下支，沒想到暴力dfs完全可以通過。

代碼：

#include <iostream> #include <cstring> using namespace std; int a[51],b[51]; int n,m; int aaa[51];bool check(int i) //就在于是理解題意 { for(i;i<=50;i++) if(aaa[i]>0)return false;return true; } int folding(int flag) {// int aaa[51];memset(aaa,0,sizeof(aaa));for(int i=0;i<=50;i++)aaa[i]=a[i];int theright=flag+1;while( !check(theright) ){aaa[flag]+=aaa[theright];aaa[theright]=0;theright++;flag--;}flag=0;while(aaa[flag]==0)flag++;int thenow=31;for(;flag<=50&&thenow<=50;flag++)a[thenow++]=aaa[flag];thenow=0;for(int i=31;i<=50;i++)if(a[i]!=0)thenow++;return thenow; } bool dfs(int nn) {int thea[51];memset(thea,0,sizeof(thea));for(int i=1+30;i<=nn+30;i++)thea[i]=a[i];if(nn<=m){if(nn==m){for(int j=31;j<=50;j++)if(a[j]!=b[j])return false;cout<<"S"<<endl;return true;}return false;}for(int i=1+30;i<nn+30;i++) //這里在看一下{int thenn=folding(i);bool haha= dfs(thenn);if(haha)return true;for(int i=31;i<=nn+30;i++)a[i]=thea[i];}return false; }int main() //如果是多個要注意每次都要初始化的。 {cin>>n;for(int i=1+30;i<=n+30;i++)cin>>a[i];cin>>m;for(int i=1+30;i<=m+30;i++)cin>>b[i];if(n==m){if(a[31]==b[31]){for(int i=31;i<=n+30;i++)if(a[i]!=b[i]){cout<<"N"<<endl;return 0;}cout<<"S"<<endl;return 0;}else{int bao=n;for(int i=31;i<=n+30;i++)if(a[i]!=b[30+bao]){cout<<"N"<<endl;return 0;}elsebao--;cout<<"S"<<endl; return 0;}}bool haha =dfs(n);if(!haha)cout<<"N"<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的Codeforces Gym 101473D Folding Machine （暴力搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

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