UVA 10118 Free Candies（记忆化搜索）

我会带着你远行 2021-12-18 06:37 173阅读 0赞

这道题像了很长时间才想明白了思路，没有明显的边界状态，状态转移也不能仅仅依靠一个dp数组。

dp\[i\]\[j\]\[k\]\[l\] 代表四堆糖果分别拿了ijkl个还能拿到的最多糖果对数（是还能拿到，不算已经拿到的），can数组存储题目输入给出的糖果，top数组表示四堆糖果都拿到了第几个（就是为了简化代码），递推边界为count\_bits(S) == 5 或者所有的糖果都被拿光 count\_bits计算的是一个数二进制有多少位是1

1 #include<cstdio>
     2 #include<cmath>
     3 #include<cstring>
     4 #include<algorithm>
     5 #include<map>
     6 #include<set>
     7 #include<vector>
     8 #include<iostream>
     9 #define PB push_back
    10 #define POB pop_back
    11 #define PII pair<int, int>
    12 #define PDD pair<double, double>
    13 #define rep(i, a, b) for(int i = a ; i < b ; i++)
    14 #pragma comment(linker, "/STACK:1024000000,1024000000")
    15 #ifdef WIN32
    16 #define INT64 "%I64d"
    17 #define UINT64 "%I64u"
    18 #else
    19 #define INT64 "%lld"
    20 #define UINT64 "%llu"
    21 #endif
    22 typedef long long LL;
    23 typedef unsigned long long ULL;
    24 using namespace std;
    25 const int maxn = 41;
    26 int dp[maxn][maxn][maxn][maxn];
    27 int can[maxn][4]; int top[5];
    28 int n;
    29 inline int count_bits(int x){
    30     x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
    31     x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
    32     x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
    33     x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
    34     x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
    35     return x;
    36 }
    37 int DP(int S) { //S 表示篮子里的糖果
    38     int& cnt = dp[top[0]][top[1]][top[2]][top[3]];
    39     if(cnt != -1) return cnt;
    40     if(count_bits(S) == 5) return cnt = 0;
    41     for(int i = 0 ; i < 4 ; i++) {
    42         if(top[i] >= n) continue;
    43         top[i]++;
    44         int t = 1 << can[top[i]][i];
    45         if(S & t) cnt = max(cnt, DP(S & (~t)) + 1);
    46         else cnt = max(cnt, DP(S | t));
    47         top[i]--;
    48     }
    49     return cnt = max(cnt, 0);
    50 }
    51 int main()
    52 {
    53     while(scanf("%d", &n) == 1 && n) {
    54         memset(dp, -1, sizeof dp);
    55         memset(top, 0, sizeof top);
    56         for(int i = 1 ; i <= n ; i++)
    57             for(int j = 0 ; j < 4 ; j++)scanf("%d", &can[i][j]);
    58         printf("%d\n", DP(0));
    59     }
    60     return 0;
    61 }

转载于:https://www.cnblogs.com/tooyoungtoosimple/p/4772385.html