这题有个小技巧, 按一个键两次等于没按,所以如果depsum > 16的话其实不用做深搜到depsum次,而只要16次就可以了。
/* ID: yingzho1 LANG: C++ TASK: lamps */ #include <iostream> #include <fstream> #include <string> #include <map> #include <vector> #include <set> #include <algorithm> #include <stdio.h> #include <queue> #include <cstring> using namespace std; ifstream fin("lamps.in"); ofstream fout("lamps.out"); int N, depsum; bool check(string s, vector<int> &on, vector<int> &off) { ; i < on.size(); i++) { ') return false; } ; i < off.size(); i++) { ') return false; } return s.size(); } void dfs(set<string> &res, int c1, int c2, int c3, int c4, string s, vector<int> &on, vector<int> &off, int dep) { if (check(s, on, off)) { == ) { res.insert(s); //return; } } || dep > depsum) return; string pre = s; ) { dfs(res, c1+, c2, c3, c4, s, on, off, dep+); ; i < s.size(); i++) { '; '; } dfs(res, c1+, c2, c3, c4, s, on, off, dep+); } s = pre; ) { dfs(res, c1, c2+, c3, c4, s, on, off, dep+); ; i < s.size(); i++) { == ) { '; '; } } dfs(res, c1, c2+, c3, c4, s, on, off, dep+); } s = pre; ) { dfs(res, c1, c2, c3+, c4, s, on, off, dep+); ; i < s.size(); i++) { == ) { '; '; } } dfs(res, c1, c2, c3+, c4, s, on, off, dep+); } s = pre; ) { dfs(res, c1, c2, c3, c4+, s, on, off, dep+); ; i < s.size(); i++) { == ) { '; '; } } dfs(res, c1, c2, c3, c4+, s, on, off, dep+); } s = pre; } int main() { fin >> N >> depsum; '); int n; vector<int> on, off; //cout << N << " " << depsum << endl; ) on.push_back(n-); ) off.push_back(n-); //for (int i = 0; i < on.size(); i++) cout << on[i] << endl; //for (int i = 0; i < off.size(); i++) cout << off[i] << endl; set<string> res; dfs(res, , , , , s, on, off, ); vector<string> ret; for (set<string>::iterator it = res.begin(); it != res.end(); it++) ret.push_back(*it); sort(ret.begin(), ret.end()); ) { fout << "IMPOSSIBLE" << endl; ; } ; i < ret.size(); i++) { fout << ret[i] << endl; } ; }