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

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。

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

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

#include <bits/stdc++.h>
using namespace std;

int n, a[21], l[21], m[21][21], res = 0;
bool md[21];

bool check(int day) {
        if (l[day] == 0) return 1;
        for (int j = 1; j <= l[day]; ++j) {
                if (!md[m[day][j]]) {
                        return 1;
                }
        }
        return 0;
}

int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
                scanf("%d", &a[i]);
        }
        for (int i = 1; i <= n; ++i) {
                scanf("%d", &l[i]);
                for (int j = 1; j <= l[i]; ++j) {
                        scanf("%d", &m[i][j]);
                }
        }
        for (int f = 0; f <= (1 << n) - 1; ++f) {
                memset(md ,0, sizeof(md));
                int tmp = f, ans = 0, day = 1;
        //        printf("%d\n", f);
                while (tmp) {
                        if (tmp & 1) {
                                if (!check(day)) {
                                        //printf("check failed:%d\n", day);
                                        goto end;
                                }
                                md[day] = 1;
                                ans += a[day];
                        }
                        tmp >>= 1;
                        ++day;
                }
                res = max(res, ans);
                end :;
        }
        printf("%d\n", res);
    return 0;
}

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

最佳答案

月排行榜 / 总排行榜

学习编程中的Ben

2023-8-5 13:27:23

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

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

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 21;
int n, a[maxn], l[maxn];
vector<int> m[maxn];
int dp[1<<maxn];

bool check(int day, int state) {
    if (l[day] == 0) return true;
    for (int j = 0; j < l[day]; ++j) {
        int d = m[day][j];
        if (state & (1 << d)) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> l[i];
        m[i].resize(l[i]);
        for (int j = 0; j < l[i]; ++j) {
            cin >> m[i][j];
        }
    }
    
    for (int state = 0; state < (1 << n); ++state) {
        dp[state] = 0;
    }

    for (int i = 0; i < n; ++i) {
        for (int state = 0; state < (1 << n); ++state) {
            if (check(i, state)) {
                dp[state | (1 << i)] = max(dp[state | (1 << i)], dp[state] + a[i]);
            }
        }
    }
    
    int answer = 0;
    for (int state = 0; state < (1 << n); ++state) {
        answer = max(answer, dp[state]);
    }
    
    cout << answer << endl;

    return 0;
}

测试样例：
输入：

3
1 2 3
1 0
0
2 1 2

输出：

5

解题思路解析：

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

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

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

跳转到最佳答案楼层

学习编程中的Ben

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

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

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 21;
int n, a[maxn], l[maxn];
vector<int> m[maxn];
int dp[1<<maxn];

bool check(int day, int state) {
    if (l[day] == 0) return true;
    for (int j = 0; j < l[day]; ++j) {
        int d = m[day][j];
        if (state & (1 << d)) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> l[i];
        m[i].resize(l[i]);
        for (int j = 0; j < l[i]; ++j) {
            cin >> m[i][j];
        }
    }
    
    for (int state = 0; state < (1 << n); ++state) {
        dp[state] = 0;
    }

    for (int i = 0; i < n; ++i) {
        for (int state = 0; state < (1 << n); ++state) {
            if (check(i, state)) {
                dp[state | (1 << i)] = max(dp[state | (1 << i)], dp[state] + a[i]);
            }
        }
    }
    
    int answer = 0;
    for (int state = 0; state < (1 << n); ++state) {
        answer = max(answer, dp[state]);
    }
    
    cout << answer << endl;

    return 0;
}

测试样例：
输入：

3
1 2 3
1 0
0
2 1 2

输出：

5

解题思路解析：

该题目是一个动态规划问题，可以使用位运算进行状态压缩处理。首先定义dp[i]表示蜗蜗在第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  表示总天数。

下面是修改后的代码：

#include <bits/stdc++.h>
using namespace std;

int n, a[21], l[21], m[21][21], dp[21][1 << 21];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[ i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &l[ i]);
        for (int j = 1; j <= l[ i]; ++j) {
            scanf("%d", &m[ i][j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < (1 << n); ++j) {
            dp[ i][j] = dp[i-1][j] + a[ i];
            for (int k = 1; k <= l[ i]; ++k) {
                if (j & (1 << (m[ i][k]-1))) {
                    dp[ i][j] = max(dp[ i][j], dp[i-1][j-(1 << (m[ i][k]-1))] + a[ i]);
                }
            }
        }
    }
    int max_happiness = 0;
    for (int j = 0; j < (1 << n); ++j) {
        max_happiness = max(max_happiness, dp[n][j]);
    }
    printf("%d\n", max_happiness);
    return 0;
}

希望能帮助到你！

zhangjinxuan

一个爆零，一个寄 7 个点

学习编程中的Ben

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

Ewan-Ahiouy

链接？

zhangjinxuan

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

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

学习编程中的Ben

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

emQAQ