250pt
在一个10^9 * 10^9大的剧院里，有最多47个位子有人，然后有一对couple想找一对左右相邻的位子，问有多少种选择方式。
思路：
总共有 n * （m-1）种方案，然后扣掉有人位置占掉的方案即可。
这里占掉位置我用一个set存储，正好可以去重。。
1 #line 7 "TheMoviesLevelOneDivOne.cpp" 2 #include <cstdlib> 3 #include <cctype> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <vector> 9 #include <string> 10 #include <iostream> 11 #include <sstream> 12 #include <map> 13 #include <set> 14 #include <queue> 15 #include <stack> 16 #include <fstream> 17 #include <numeric> 18 #include <iomanip> 19 #include <bitset> 20 #include <list> 21 #include <stdexcept> 22 #include <functional> 23 #include <utility> 24 #include <ctime> 25 using namespace std; 26 27 #define PB push_back 28 #define MP make_pair 29 30 #define REP(i,n) for(i=0;i<(n);++i) 31 #define FOR(i,l,h) for(i=(l);i<=(h);++i) 32 #define FORD(i,h,l) for(i=(h);i>=(l);--i) 33 34 typedef vector<int> VI; 35 typedef vector<string> VS; 36 typedef vector<double> VD; 37 typedef long long LL; 38 typedef pair<int,int> PII; 39 40 41 class TheMoviesLevelOneDivOne 42 { 43 public: 44 long long find(int n, int m, vector <int> row, vector <int> seat) 45 { 46 long long ans = n; 47 ans =ans * (m - 1); 48 set< PII > S; 49 for (int i = 0; i < row.size(); ++i){ 50 if (seat[i] > 1) S.insert(make_pair(row[i], seat[i])); 51 if (seat[i] + 1 <= m) S.insert(make_pair(row[i], seat[i] + 1)); 52 } 53 ans -= S.size(); 54 return ans; 55 } 56 57 };
500pt
题意：一个人看电影，该人有一个scare值，并且没看1min电影scare减1。有很多部恐怖电影，每部电影长度不同(length[i])，且每部都有一个瞬间增加scare(s[i])值的时刻。如果scare值小于0，则这个人就会睡着，不能再看电影。请问他安排一个电影观看顺序，使得他能看尽可能多的电影。如果有多组观看顺序看到的电影数相同，则输出字典序最小的。(电影数量小等于20)
思路：
状态压缩。。
1 #line 7 "TheMoviesLevelTwoDivOne.cpp" 2 #include <cstdlib> 3 #include <cctype> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <vector> 9 #include <string> 10 #include <iostream> 11 #include <sstream> 12 #include <map> 13 #include <set> 14 #include <queue> 15 #include <stack> 16 #include <fstream> 17 #include <numeric> 18 #include <iomanip> 19 #include <bitset> 20 #include <list> 21 #include <stdexcept> 22 #include <functional> 23 #include <utility> 24 #include <ctime> 25 using namespace std; 26 27 #define PB push_back 28 #define MP make_pair 29 30 #define REP(i,n) for(i=0;i<(n);++i) 31 #define FOR(i,l,h) for(i=(l);i<=(h);++i) 32 #define FORD(i,h,l) for(i=(h);i>=(l);--i) 33 34 typedef vector<int> VI; 35 typedef vector<string> VS; 36 typedef vector<double> VD; 37 typedef long long LL; 38 typedef pair<int,int> PII; 39 int dp[1 << 20]; 40 41 class TheMoviesLevelTwoDivOne 42 { 43 public: 44 vector <int> find(vector <int> L, vector <int> scary) 45 { 46 int n = L.size(); 47 memset(dp, 0, sizeof(dp)); 48 for (int i = 1; i < (1 << n); ++i){ 49 int level = 74; 50 for (int j = 0; j < n; ++j) 51 if (!(i & (1 << j))) level += 47 - L[j]; 52 for (int j = 0; j < n; ++j) if (i & (1 << j)) 53 if (level >= scary[j] && level + 47 - L[j] >= 0) 54 dp[i] = max(dp[i], dp[i ^ (1 << j)] + 1); 55 } 56 vector<int> ans; 57 int x = 74, mask = (1 << n) - 1; 58 while (mask > 0){ 59 for (int i = 0; i < n; ++i) if (mask & (1 << i)) 60 if (dp[mask] == 0 || 61 (x >= scary[i] && x + 47 - L[i] >= 0 && dp[mask ^ (1 << i)] == dp[mask] - 1)){ 62 ans.PB(i); 63 mask ^= (1 << i); 64 x += 47 - L[i]; 65 break; 66 } 67 } 68 return ans; 69 } 70 };