论MC中的数学

yangff

随便写写懒的优化了

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <queue>
   
4. using namespace std;
   
5. // 0 water 1 veg
   
6. int dp[9][(1<<9)][1<<9];
   
7. 
   
8. bool checkok(int now, int upper, int upper1) {
   
9.         if (upper & 1){
   
10.                 if ((now & 1) && (upper1 & 1) && ((upper >> 1) & 1))
    
11.                         return false;
    
12.         }
    
13.         if ((upper >> 8) & 1){
    
14.                 if (((now>>8) & 1) && ((upper1>>8) & 1) && ((upper >> 7) & 1))
    
15.                         return false;
    
16.         }
    
17.         for (int i = 1; i < 8; i++) {
    
18.                 if ((upper >> i) & 1) {
    
19.                         if ( ((upper >> (i - 1))&1) && ((upper >> (i + 1))&1) && ((now >> (i))&1) && ((upper1 >> (i))&1)) {
    
20.                                 return false;
    
21.                         }
    
22.                 }
    
23.         }
    
24.         return true;
    
25. }
    
26. 
    
27. 
    
28. int count1(int x){
    
29.         int cnt = 0;
    
30.         while (x){
    
31.                 cnt+=x&1;
    
32.                 x >>= 1;
    
33.         }
    
34.         return cnt;
    
35. }
    
36. 
    
37. int main(){
    
38.         for (int i = 0; i < (1<<9); i++){
    
39.                 dp[0][i][(1 << 9) - 1] = count1(i);
    
40.         }
    
41. 
    
42.         for (int i = 1; i < 9; i++){
    
43.                 for (int now = 0; now < (1<<9); now++){
    
44.                         for (int upper = 0; upper < (1<<9); upper++)
    
45.                                 for (int upper1 = 0; upper1 < (1<<9); upper1++){
    
46.                                         if (checkok(now, upper, upper1)) {
    
47.                                                 dp[i][now][upper] = max(dp[i][now][upper], dp[i - 1][upper][upper1] + count1(now));
    
48.                                         }
    
49.                         }
    
50.                 }
    
51.         }
    
52. 
    
53.         int ans = 0;
    
54.         for (int upper = 0; upper < (1<<9); upper++) {
    
55.                 for (int upper1 = 0; upper1 < (1<<9); upper1 ++){
    
56.                         if (checkok((1<<9) - 1, upper, upper1)) {
    
57.                                 ans = max(ans, dp[8][upper][upper1]);
    
58.                         }
    
59.                 }
    
60.         }
    
61.         printf("%d\n", ans);
    
62. 
    
63. }
    

复制代码