题目给你一个串, 串是严格的 1 – n 的排列,里面的数是随机的

把这个串里面的数字分别输出//先预处理,对于给出的串能找到里面的最大数,再 DFS 处理

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
bool Jug[100];
string num[55];
string str;
int len,Num;
stack<int> Sum;
bool Dfs(int n) {
if(n >= len) {
if(Jug[Num] == true) return true;
return false;
}
int a,b;
if(n <len) a = str[n] - '0';
if(n < len-1) b = a*10 + str[n+1] - '0';
if(a==0) return false;
if(Jug[a] == false && n <len) {
Jug[a] = true;
if(Dfs(n+1))
{
Sum.push(a);
return true;
}
Jug[a] = false;
}
if(b <= 50 && Jug[b] == false && n < len-1) {
Jug[b] = true;
if(Dfs(n+2)) {
Sum.push(b);
return true;
}
Jug[b] = false;
}
return false;
}
int main() {
num[1] = "1";
for(int i = 2; i <= 50; ++i) if(i < 10) num[i] = (num[i-1] + char(i + '0'));
else num[i] = (num[i-1] + char(i/10 + '0') + char (i % 10 + '0'));
for(int i = 1; i <= 50; ++i) sort(num[i].begin(),num[i].end());
////////////// while(cin >> str) {
Num = 0;
memset(Jug,false,sizeof(Jug));
while(!Sum.empty()) Sum.pop();
string s = str;
sort(s.begin(),s.end());
for(int i = 1; i <= 50; ++i) if(s == num[i]) {
Num = i; break;
}
//cout << Num << endl;
len = str.length();
Dfs(0);
while(!Sum.empty()) {
cout << Sum.top() << " ";
Sum.pop();
}
cout << endl;
}
}
05-11 20:14