url: https://www.luogu.com.cn/problem/P4095

tag:
动态规划，背包DP，进制，枚举

思路：
多重背包问题为基础，做两次01背包，前一次后一次，之后对于每次询问的id就跳过那个id求可能的最大值。

代码：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
typedef long long LL;  
const int N = 100010;  
struct node{  
    int id;LL s;  
}w[N], v[N];  
LL f1[N][1010], f2[N][1010];  
int idx, m, n;  
int main()  
{  
    cin >> n;  
    for (int i = 1; i <= n;  i++)  
    {  
        int cw, cv, c;  
        cin >> cw >> cv >> c;  
        int now = 1;  
        while (now <= c)  
        {  
            w[++idx].s = cw * now, v[idx].s = cv * now;  
            w[idx].id = i, v[idx].id = i;  
            c -= now, now *= 2;  
        }  
        if(c) {  
            w[++idx].s = cw * c, v[idx].s = cv * c;  
            w[idx].id = i, v[idx].id = i;  
        }  
    }  
    cin >> m;  
    n = idx;  
    for (int i = 1; i <= n; i ++)  
    {  
        for (int j = 0; j <= 1000; j ++) f1[i][j] = f1[i - 1][j];  
        for (int j = 1000; j >= w[i].s; j --)  
        {  
            f1[i][j] = max(f1[i][j], f1[i - 1][j - w[i].s] + v[i].s);  
        }  
    }  
    for (int i = n; i >= 1; i --)  
    {  
        for (int j = 0; j <= 1000; j ++) f2[i][j] = f2[i + 1][j];  
        for (int j = 1000; j >= w[i].s; j --)  
        {  
            f2[i][j] = max(f2[i][j], f2[i + 1][j - w[i].s] + v[i].s);  
        }  
    }  
    for (int k = 1; k <= m; k ++)  
    {  
        int cn, V;  
        cin >> cn >> V;  
        cn ++;  
        LL ans = 0;  
        int l = 0, r = 0;  
        while (w[l + 1].id < cn && l < n) ++ l;  
        r = l;  
        while (w[r + 1].id <= cn && r < n) ++ r;  
        for (int j = 0; j <= V; j++)  
        {  
            ans = max(ans, f1[l][j] + f2[r + 1][V - j]);  
        }  
        cout << ans << endl;  
    }  
    return 0;  
}

问题描述

小C在学习二进制运算，他了解到每个非负整数都有其二进制表示。例如，整数 5 可以被表示为二进制 "101"，整数 11 可以被表示为二进制 "1011"，并且除了 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 变为 0，每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。现在小C想知道，给定一个十进制数 N，它的二进制反码对应的十进制数是多少。

测试样例

样例1：

输入：N = 5
输出：2

样例2：

输入：N = 10
输出：5

样例3：

输入：N = 0
输出：1

代码：

int solution(int N) {
    if (N == 0) {
        return 1;
    }
    int bits = std::log2(N) + 1;
    std::bitset<32> binary(N);
    std::bitset<32> inverted = ~binary;
    int result = (inverted.to_ulong() & ((1 << bits) - 1));
    return result;
}

解释

• std::log2(N) + 1:

  • 计算 N 的二进制位数。

• std::bitset<32> binary(N);:

  • 这行代码将整数 N 转换为一个 32 位的二进制表示。

• std::bitset<32> inverted = ~binary;:

  • 这行代码对 binary 进行按位取反操作，得到 inverted。

• int result = inverted.to_ulong();:

  • 这行代码将 inverted 转换回无符号长整型。

• (1 << bits) - 1:

  • 生成一个掩码，只保留低 bits 位。

• inverted.to_ulong() & ((1 << bits) - 1):

  • 只取 inverted 的低 bits 位，忽略高位部分。

url: https://www.luogu.com.cn/problem/P2851

tag:
动态规划，背包DP，进制，USACO，2006

思路：
可以用背包来做。用 f[i] 表示john付i块钱时最少的硬币数，用 g[i] 表示店主找零i块钱时最少的硬币数，对于f来说，因为硬币数量有限所以需要用多重背包来完成。而对于g来说因为硬币无限多，所以可以用完全背包。对于体积上限取多少可以参考： https://www.luogu.com.cn/article/sd0bx6un

代码：

#include <iostream>  
#include <cstring>  
#include <cstdio>  
#include <algorithm>  
using namespace std;  
typedef long long LL;  
const int N = 10010, M = 150;  
int c[M], v[M];  
int f[N + M * M], g[N + M * M];  
int n, t, mx, sum;  
int main()  
{  
    cin >> n >> t;  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> v[i];  
        mx = max(mx, v[i] * v[i]);  
    }  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> c[i];  
        sum += v[i] * c[i];  
    }  
    if (sum < t)  
    {  
        cout << -1 << endl;  
        return 0;  
    }  
    memset(f, 0x3f, sizeof f);  
    memset(g, 0x3f, sizeof g);  
    g[0] = 0;  
    f[0] = 0;  
    for (int i = 1; i <= n; i ++)  
        for (int j = v[i]; j <= mx; j ++)  
            g[j] = min(g[j], g[j - v[i]] + 1);  
    for (int i = 1; i <= n; i ++)  
    {  
        for (int j = 1; j <= c[i]; j *= 2)  
        {  
            for (int k = mx + t; k >= j * v[i]; k --)  
                f[k] = min(f[k], f[k - j * v[i]] + j);  
            c[i] -= j;  
        }  
        if (c[i])  
            for (int k = mx + t; k >= c[i] * v[i]; k --)  
                f[k] = min(f[k], f[k - c[i] * v[i]] + c[i]);  
    }  
    int res = 0x3f3f3f3f;  
    for (int i = t; i <= t + mx; i ++)  
        res = min(res, f[i] + g[i - t]);  
    cout << (res == 0x3f3f3f3f ? -1 : res) << endl;  
    return 0;  
}