html网页制作下载/seo网络优化专员是什么意思
https://www.luogu.org/problemnew/show/P1118
本题的特点在于必须找到第一个字典序最小的解, 就退出递归. 之前写得方法:
vector<string> ans;
用ans保存打印好的答案, 然后排序找字典序最小解. 此法错误,
- TLE
- WA, 因为默认1 10 2 3 … 9 是字符串序列的最小字典序.
之后我改为找到解之后就退出程序, 但是发现用排序树找到的第一个解不是字典序最小的解.
而用for外夹紧的dfs, 配合vis记录路径, 找到的以一个解是字典序最小的解.
#include <bits/stdc++.h>
#define FF(a,b) for(int a=0;a<b;a++)
#define F(a,b) for(int a=1;a<=b;a++)
#define LEN 110
#define bug(x) cout<<#x<<"="<<x<<endl;using namespace std;int C[50][50];
int N,Sum;
int x[50];
int cp[50];
int vis[50];int C_(int n,int m){if(C[n][m]) return C[n][m];if(m==0){C[n][m]=1;return C[n][m];}if(m==n){C[n][m]=1;return C[n][m];}else{C[n][m]=C_(n-1,m-1)+C_(n-1,m);return C[n][m];}
}int calc_sum(int t){int res=0;F(i,t){res+=cp[i]*x[i];}return res;
}string num2str(int m){char buf[100];sprintf(buf,"%d",m);return string(buf);
}string x2str(){string ans;F(i,N){ans+=num2str(x[i]);if(i<N) ans+=" ";}return ans;
}bool dfs(int t,int sum,int num) {//t:当前步，1开始；sumif(sum>Sum){ //剪枝return 0;}if (t > N){if(sum==Sum){string s=x2str();cout<<s;exit(0);return 1;}}//入栈vis[num]=1;x[t]=num;//遍历int t_sum=calc_sum(t); //特别注意,在放置好最后一个数字后if(t==N) dfs(t+1,t_sum,0); //因为vis全为1, 所以不会触发下一个dfs进入终态else //所以要特判F(i,N)if(!vis[i]){ dfs(t+1,t_sum,i);}//出栈vis[num]=0;
}
int main()
{freopen("./in","r",stdin);cin>>N>>Sum;F(i,N){cp[i]=C_(N-1,i-1);}dfs(0,0,0);return 0;
}