SRM 562 DIV2

1、第一个，水题，直接求最大值即可，略。

2、根据题目，clipboard最大的时候是50，则可以得到，当粘贴超过50次以后，每次增长的个数是肯定是固定个数。

　　写的时候为了保险，把50换到了100多。

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <map>
 6 #include <algorithm>
 7 #include <stack>
 8 #include <queue>
 9 #include <cmath>
10 using namespace std;
11 typedef long long ll;
12 const int sz_pix = 160;
13 int num[sz_pix];
14 bool judge[sz_pix][sz_pix];
15 class PastingPaintingDivTwo {
16 public:
17     long long countColors(vector<string> clipboard, int T) {
18         int r = clipboard.size();
19         int c = clipboard[0].size();
20         for (int i = 0; i < sz_pix; i++)
21             for (int j = 0; j < sz_pix; j++) {
22                 num[i] = 0;
23                 judge[i][j] = false;
24             }
25         for (int i = 0; i < 105; i++) {
26             for (int a = 0; a < r; a++) {
27                 for (int b = 0; b < c; b++) {
28                     if ((!judge[i + a][i + b]) && (clipboard[a][b] == 'B')) {
29                         judge[i + a][i + b] = true;
30                         num[i]++;
31                     }
32                 }
33             }
34         }
35         if (T > 103) {
36             ll inc = num[102] ;
37             ll remain = T - 103;
38             ll tmp = remain * inc;
39             ll res = tmp;
40             for (int i = 0; i < 103; i++) {
41                 res += num[i];
42             }
43             return res;
44         }
45         ll res = 0;
46         for (int i = 0; i < T; i++) {
47             res += num[i];
48         }
49         return res;
50 
51     }
52 };

3、动态规划+状态压缩的问题。

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <map>
 6 #include <algorithm>
 7 #include <stack>
 8 #include <queue>
 9 #include <cmath>
10 using namespace std;
11 typedef long long ll;
12 ll num[15][15][1 << 14];
13 
14 bool path[15][15];
15 class RandomOption {
16 public:
17     double getProbability(int keyCount, vector<int> badLane1,
18             vector<int> badLane2) {
19 
20         for (int i = 0; i < keyCount; i++)
21             num[0][i][1 << i] = 1;
22 
23         int sz = badLane1.size();
24         for (int i = 0; i < sz; i++) {
25             int s = badLane1[i];
26             int e = badLane2[i];
27             path[s][e] = path[e][s] = true;
28         }
29         for (int i = 1; i < keyCount; i++) {
30             for (int j = 0; j < keyCount; j++) {
31                 for (int pre = 0; pre < (1 << keyCount); pre++) {
32                     for (int k = 0; k < keyCount; k++) {
33                         if (path[j][k] || (pre & (1 << k)))
34                             continue;
35                         int now = pre | (1 << k);
36                         num[i][k][now] += num[i - 1][j][pre];
37                     };
38                 }
39             }
40 
41         }
42         double all = 1;
43         int keyCount1 = keyCount;
44         while (keyCount1) {
45             all *= keyCount1;
46             keyCount1--;
47         }
48         double pos = 0;
49         for (int i = 0; i < keyCount; i++) {
50             pos += num[keyCount - 1][i][(1 << keyCount) - 1];
51         }
52 
53         double res = pos / all;
54         return res;
55     }
56 };