求助｜关于状压 dp

123****0002

2024-06-20 11:59:34

发布于：浙江

20阅读

0回复

0点赞

今天做状压dp1349. 参加考试的最大学生数时，先写了一个枚举每一行的排列，过程中枚举下一行的排列，用当前行的状态更新下一行的状态的写法，过了之后改成了过程中枚举上一行的排列，用上一行更新当前行的状态的写法，却过不了了，怎么看都没看出来哪错了，求大佬指点

写法一（可ac）：用当前行的状态更新下一行的状态


class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int m = seats.size(), n = seats[0].size(), ans = 0;
        vector<int>seq(m + 1);//第一排前面加一排，用于更新第一排的状态
        for (int i = 0; i < m; i++)
            for (char c : seats[i])
                seq[i + 1] = (seq[i + 1] << 1) | (c == '.');//所有完好座位的集合
        vector<vector<int>>f(1 << n, vector<int>(m + 1));
        for (int i = 0; i < m; i++){
            int sub = seq[i];//枚举第i行所有完好座位的子集
            do{
                int nextsub = seq[i + 1];//枚举第i+1行所有完好座位的子集
                do{
                    if (nextsub >> 1 & (nextsub | sub) || nextsub << 1 & (nextsub | sub)) continue;//左侧、右侧、左上、右上有人
                    f[nextsub][i + 1] = max(f[nextsub][i + 1], f[sub][i] + __builtin_popcount(nextsub));
                }while((nextsub = (nextsub - 1) & seq[i + 1]) | 1 && nextsub != seq[i + 1]);//枚举第i+1行所有完好座位的子集，|1是防止空集为0会使while里判断错误
            }while((sub = (sub - 1) & seq[i]) | 1 && sub != seq[i]);//枚举第i行所有完好座位的子集，|1是防止空集为0会使while里判断错误
        }
        for (int i = 0; i < 1 << n; i++) ans = max(ans, f[i][m]);
        return ans;
    }
};

写法二（wa）：用上一行更新当前行的状态


class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int m = seats.size(), n = seats[0].size(), ans = 0;
        vector<int>seq(m + 1);//第一排前面加一排，用于更新第一排的状态
        for (int i = 0; i < m; i++)
            for (char c : seats[i])
                seq[i + 1] = (seq[i + 1] << 1) | (c == '.');//所有完好座位的集合
        vector<vector<int>>f(1 << n, vector<int>(m + 1));
        for (int i = 0; i < m; i++){
            int sub = seq[i + 1];//枚举第i+1行所有完好座位的子集
            do{
                int presub = seq[i], count = __builtin_popcount(sub);//枚举第i行所有完好座位的子集
                do{
                    if (presub >> 1 & (presub | sub) || presub << 1 & (presub | sub)) continue;//左侧、右侧、左上、右上有人
                    f[sub][i + 1] = max(f[sub][i + 1], f[presub][i] + count);
                }while((presub = (presub - 1) & seq[i]) | 1 && presub != seq[i]);//枚举第i行所有完好座位的子集，|1是防止空集为0会使while里判断错误
            }while((sub = (sub - 1) & seq[i + 1]) | 1 && sub != seq[i + 1]);//枚举第i+1行所有完好座位的子集，|1是防止空集为0会使while里判断错误
        }
        for (int i = 0; i < 1 << n; i++) ans = max(ans, f[i][m]);
        return ans;
    }
};

有帮助，赞一个

去预览

0/2000

全部评论 3

最大昵称显示查看最大昵称显示查看
11

2024-07-11 来自浙江
0

123****0002

我把f的结果输出出来比对发现f[2][12]应该是0但是值为3，违反了相邻不能坐的规则

if (presub >> 1 & (presub | sub) || presub << 1 & (presub | sub)) continue;

应改成

if (sub >> 1 & (presub | sub) || sub << 1 & (presub | sub)) continue;

话说这些条件里面做运算的看的累死人，最好写的容易理解一点，避免判断多种运算符优先级

2024-06-20 来自浙江

123****0002

回复123****0002

####果然是！！，测试点留了钻空子的机会，判断是否是完全背包就直接能跑完全背包了
###单调队列优化&预处理是否是完全背包问题
####运行时间160ms

#include <stdio.h>
#include <stdlib.h>
#define arraymax 20001
#define Max(a, b) (a > b ? a : b)
int dp[arraymax];
int book[arraymax], que[arraymax];
int main(int argc, char *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    while (n--)
    {
        int k, value, cnt;
        scanf("%d%d%d", &k, &value, &cnt);
        if (cnt * k >= m)
        {
            for (int ind = k; ind <= m; ind++)
                dp[ind] = Max(dp[ind - k] + value, dp[ind]);
        }
        else
        {
            for (int ind = 0; ind < k; ind++)
            {
                int head = 0, body = 0;
                for (int jnd = 0; jnd <= (m - ind) / k; jnd++)
                {
                    int y = dp[jnd * k + ind] - jnd * value;
                    while (head < body && y >= que[body - 1])
                        body--;
                    book[body] = jnd;
                    que[body++] = y;
                    if (book[head] < jnd - cnt)
                        head++;
                    dp[jnd * k + ind] = que[head] + jnd * value;
                }
            }
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

2024-06-20 来自浙江

123****0002
回复123****0002
标题1

标题2

2024-06-20 来自浙江
0

123****0002

回复123****0002

class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int m = seats.size(), n = seats[0].size(), ans = 0;
        vector<int>seq(m + 1);//第一排前面加一排，用于更新第一排的状态
        for (int i = 0; i < m; i++)
            for (char c : seats[i])
                seq[i + 1] = (seq[i + 1] << 1) | (c == '.');//所有完好座位的集合
        vector<vector<int>>f(1 << n, vector<int>(m + 1));
        for (int i = 0; i < m; i++){
            int sub = seq[i + 1];//枚举第i+1行所有完好座位的子集
            do{
                int presub = seq[i], count = __builtin_popcount(sub);//枚举第i行所有完好座位的子集
                do{
                    if (presub >> 1 & (presub | sub) || presub << 1 & (presub | sub)) continue;//左侧、右侧、左上、右上有人
                    f[sub][i + 1] = max(f[sub][i + 1], f[presub][i] + count);
                }while((presub = (presub - 1) & seq[i]) | 1 && presub != seq[i]);//枚举第i行所有完好座位的子集，|1是防止空集为0会使while里判断错误
            }while((sub = (sub - 1) & seq[i + 1]) | 1 && sub != seq[i + 1]);//枚举第i+1行所有完好座位的子集，|1是防止空集为0会使while里判断错误
        }
        for (int i = 0; i < 1 << n; i++) ans = max(ans, f[i][m]);
        return ans;
    }
};

2024-06-20 来自浙江

123****0002
我把f的结果输出出来比对发现f[2][12]应该是0但是值为3，违反了相邻不能坐的规则

if (presub >> 1 & (presub | sub) || presub << 1 & (presub | sub)) continue;

应改成

if (sub >> 1 & (presub | sub) || sub << 1 & (presub | sub)) continue;

话说这些条件里面做运算的看的累死人，最好写的容易理解一点，避免判断多种运算符优先级
2024-06-20 来自浙江
0

全部评论 3

标题1

标题2

热门讨论