USACO Section 2.2: Party Lamps

这题有个小技巧, 按一个键两次等于没按,所以如果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;
     }

     ;
 }
上一篇:AMD and CMD are dead之KMD.js依赖可视化工具发布


下一篇:【算法笔记】B1033 旧键盘打字