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

zhangjinxuan

题目描述

蜗蜗一共有 n 天假期，在假期的第 i 天摸鱼他会得到 ai 的快乐值。如果蜗蜗每天都摸鱼的话，他会有愧疚感，所以蜗蜗制定了这么个计划：对于每一天，蜗蜗都有一个列表，如果蜗蜗在列表中的每一天都在摸鱼的话，这一天蜗蜗就不能摸鱼。现在请问蜗蜗如何摸鱼，使得他能获得的快乐值总和最大？请求出快乐值总和最大是多少。

输入格式
第一行一个整数 n 表示天数。

第二行 n 个整数 a_1,a_2,...,a_n。

接下来 n 行，对于第 i 行，先读入一个整数 l_i 表示第 i 天的列表上有几天。如果 l_i=0，也就是列表是空的话，表示第 i 天没有限制；否则，再读入 l_i 个数表示列表上列的分别是第几天，数据保证这 l_i 个数两两不同并且都不等于 i。

输出格式
一行一个整数表示答案。

是的，一道水题我都能写挂。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, a[21], l[21], m[21][21], res = 0;
   
5. bool md[21];
   
6. 
   
7. bool check(int day) {
   
8.         if (l[day] == 0) return 1;
   
9.         for (int j = 1; j <= l[day]; ++j) {
   
10.                 if (!md[m[day][j]]) {
    
11.                         return 1;
    
12.                 }
    
13.         }
    
14.         return 0;
    
15. }
    
16. 
    
17. int main() {
    
18.         scanf("%d", &n);
    
19.         for (int i = 1; i <= n; ++i) {
    
20.                 scanf("%d", &a[i]);
    
21.         }
    
22.         for (int i = 1; i <= n; ++i) {
    
23.                 scanf("%d", &l[i]);
    
24.                 for (int j = 1; j <= l[i]; ++j) {
    
25.                         scanf("%d", &m[i][j]);
    
26.                 }
    
27.         }
    
28.         for (int f = 0; f <= (1 << n) - 1; ++f) {
    
29.                 memset(md ,0, sizeof(md));
    
30.                 int tmp = f, ans = 0, day = 1;
    
31.         //        printf("%d\n", f);
    
32.                 while (tmp) {
    
33.                         if (tmp & 1) {
    
34.                                 if (!check(day)) {
    
35.                                         //printf("check failed:%d\n", day);
    
36.                                         goto end;
    
37.                                 }
    
38.                                 md[day] = 1;
    
39.                                 ans += a[day];
    
40.                         }
    
41.                         tmp >>= 1;
    
42.                         ++day;
    
43.                 }
    
44.                 res = max(res, ans);
    
45.                 end :;
    
46.         }
    
47.         printf("%d\n", res);
    
48.     return 0;
    
49. }

复制代码

写得有点类似状压，但是 8 个点寄了 6 个，不知道怎么回事，求GPT，人工解答。

最佳答案

月排行榜 / 总排行榜

学习编程中的Ben

2023-8-5 13:27:23

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

算法思路：
这是一个动态规划问题，可以使用状态压缩和位运算来解决。定义dp表示蜗蜗在第i天能够获得的最大快乐值总和。状态转移方程为：dp = max(dp[i-1], dp[j] + a)，其中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天能够获得的最大快乐值总和。然后使用一个整数state表示当前已经选择摸鱼的天数的集合，第i天是否摸鱼可以通过判断state的二进制表示中的第i位是否为1来确定。在状态转移时需要遍历前一天的所有状态，并找到满足条件的状态进行转移。最后得到的dp[(1<<n)-1]就是答案，表示选择了所有天数之后获得的最大快乐值总和。

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

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

跳转到最佳答案楼层

学习编程中的Ben

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

算法思路：
这是一个动态规划问题，可以使用状态压缩和位运算来解决。定义dp表示蜗蜗在第i天能够获得的最大快乐值总和。状态转移方程为：dp = max(dp[i-1], dp[j] + a)，其中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天能够获得的最大快乐值总和。然后使用一个整数state表示当前已经选择摸鱼的天数的集合，第i天是否摸鱼可以通过判断state的二进制表示中的第i位是否为1来确定。在状态转移时需要遍历前一天的所有状态，并找到满足条件的状态进行转移。最后得到的dp[(1<<n)-1]就是答案，表示选择了所有天数之后获得的最大快乐值总和。

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

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

isdkz

这道题目是一个经典的动态规划问题。我们可以使用状态压缩的方法来解决。

首先，我们定义一个二维数组  dp ，其中  dp[ i][j]  表示在第  i  天，状态为  j  时能够获得的最大快乐值。

然后，我们可以使用动态规划的思想来递推求解  dp  数组。具体的递推关系如下：

1. 初始化  dp[0][j]  为 0，表示第 0 天的任何状态下都无法获得快乐值。

2. 对于每一天  i ，遍历所有的状态  j ：

   a. 如果第  i  天的列表为空，即  l[ i] = 0 ，那么第  i  天的状态  j  可以直接从第  i-1  天的状态  j  转移而来，即  dp[ i][j] = dp[i-1][j] + a[ i] 。
   
   b. 如果第  i  天的列表不为空，即  l[ i] > 0 ，那么我们需要判断第  i  天的状态  j  是否满足列表中的要求。具体的判断方法如下：
   
      · 首先，我们定义一个变量  valid ，初始值为  true ，表示第  i  天的状态  j  满足列表中的要求。
      
      · 然后，我们遍历第  i  天的列表中的每一天  k ：
      
        · 如果第  k  天的状态  j  为 0，表示第  k  天在状态  j  下没有摸鱼，那么第  i  天的状态  j  不满足列表中的要求，我们将  valid  设置为  false 。
        
        · 如果第  k  天的状态  j  不为 0，表示第  k  天在状态  j  下摸了鱼，那么第  i  天的状态  j  满足列表中的要求。
        
      · 最后，如果  valid  为  true ，那么第  i  天的状态  j  可以从第  i-1  天的状态  j  转移而来，即  dp[ i][j] = dp[i-1][j] + a[ i] 。
      
3. 最后，我们遍历所有的状态  j ，找到能够获得的最大快乐值  max_happiness ，即  max_happiness = max(dp[n][j]) ，其中  n  表示总天数。

下面是修改后的代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, a[21], l[21], m[21][21], dp[21][1 << 21];
   
5. 
   
6. int main() {
   
7.     scanf("%d", &n);
   
8.     for (int i = 1; i <= n; ++i) {
   
9.         scanf("%d", &a[ i]);
   
10.     }
    
11.     for (int i = 1; i <= n; ++i) {
    
12.         scanf("%d", &l[ i]);
    
13.         for (int j = 1; j <= l[ i]; ++j) {
    
14.             scanf("%d", &m[ i][j]);
    
15.         }
    
16.     }
    
17.     for (int i = 1; i <= n; ++i) {
    
18.         for (int j = 0; j < (1 << n); ++j) {
    
19.             dp[ i][j] = dp[i-1][j] + a[ i];
    
20.             for (int k = 1; k <= l[ i]; ++k) {
    
21.                 if (j & (1 << (m[ i][k]-1))) {
    
22.                     dp[ i][j] = max(dp[ i][j], dp[i-1][j-(1 << (m[ i][k]-1))] + a[ i]);
    
23.                 }
    
24.             }
    
25.         }
    
26.     }
    
27.     int max_happiness = 0;
    
28.     for (int j = 0; j < (1 << n); ++j) {
    
29.         max_happiness = max(max_happiness, dp[n][j]);
    
30.     }
    
31.     printf("%d\n", max_happiness);
    
32.     return 0;
    
33. }
    

复制代码

希望能帮助到你！

zhangjinxuan

一个爆零，一个寄 7 个点

学习编程中的Ben

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

Ewan-Ahiouy

链接？

zhangjinxuan

学习编程中的Ben 发表于 2023-8-5 14:50
可以给我链接吗,我写一下

链接不方便，这个是课程里面的题目

学习编程中的Ben

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

emQAQ