[已解决]有一道水题写挂了，什么情况

学习编程中的Ben

问题分析：
根据题目描述，蜗蜗每天都有一个列表，如果蜗蜗在列表中的每一天都在摸鱼的话，这一天蜗蜗就不能摸鱼。我们需要找出蜗蜗摸鱼能够获得的快乐值总和最大。

算法思路：
这是一个动态规划问题，可以使用状态压缩和位运算来解决。定义dp[i]表示蜗蜗在第i天能够获得的最大快乐值总和。状态转移方程为：dp[i] = max(dp[i-1], dp[j] + a[i])，其中j是满足以下条件的所有天数：第i天没有要求，并且第j天的限制与第i天无冲突。

代码实现：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. const int maxn = 21;
   
7. int n, a[maxn], l[maxn];
   
8. vector<int> m[maxn];
   
9. int dp[1<<maxn];
   
10. 
    
11. bool check(int day, int state) {
    
12.     if (l[day] == 0) return true;
    
13.     for (int j = 0; j < l[day]; ++j) {
    
14.         int d = m[day][j];
    
15.         if (state & (1 << d)) {
    
16.             return false;
    
17.         }
    
18.     }
    
19.     return true;
    
20. }
    
21. 
    
22. int main() {
    
23.     cin >> n;
    
24.     for (int i = 0; i < n; ++i) {
    
25.         cin >> a[i];
    
26.     }
    
27.     for (int i = 0; i < n; ++i) {
    
28.         cin >> l[i];
    
29.         m[i].resize(l[i]);
    
30.         for (int j = 0; j < l[i]; ++j) {
    
31.             cin >> m[i][j];
    
32.         }
    
33.     }
    
34.    
    
35.     for (int state = 0; state < (1 << n); ++state) {
    
36.         dp[state] = 0;
    
37.     }
    
38. 
    
39.     for (int i = 0; i < n; ++i) {
    
40.         for (int state = 0; state < (1 << n); ++state) {
    
41.             if (check(i, state)) {
    
42.                 dp[state | (1 << i)] = max(dp[state | (1 << i)], dp[state] + a[i]);
    
43.             }
    
44.         }
    
45.     }
    
46.    
    
47.     int answer = 0;
    
48.     for (int state = 0; state < (1 << n); ++state) {
    
49.         answer = max(answer, dp[state]);
    
50.     }
    
51.    
    
52.     cout << answer << endl;
    
53. 
    
54.     return 0;
    
55. }
    

复制代码

测试样例：
输入：

1. 
   
2. 3
   
3. 1 2 3
   
4. 1 0
   
5. 0
   
6. 2 1 2
   

复制代码

输出：

1. 
   
2. 5
   

复制代码

解题思路解析：

该题目是一个动态规划问题，可以使用位运算进行状态压缩处理。首先定义dp[i]表示蜗蜗在第i天能够获得的最大快乐值总和。然后使用一个整数state表示当前已经选择摸鱼的天数的集合，第i天是否摸鱼可以通过判断state的二进制表示中的第i位是否为1来确定。在状态转移时需要遍历前一天的所有状态，并找到满足条件的状态进行转移。最后得到的dp[(1<<n)-1]就是答案，表示选择了所有天数之后获得的最大快乐值总和。

希望以上解答对您有帮助！如果还有其他问题，请继续提问。

如果回答对你有帮助，请给我一个最佳答案！

学习编程中的Ben

可以给我链接吗,我写一下

学习编程中的Ben

zhangjinxuan 发表于 2023-8-5 14:57
链接不方便，这个是课程里面的题目

emQAQ