【DP完全背包】A+B Problem（再升级）

迈不过友情╰ 2024-03-30 11:53 97阅读 0赞

[P1832 A+B Problem（再升级） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1832 A_B Problem_ - _ _ _ _luogu.com.cn]

题意：

![f8ea0005c30446bcb14be83a58e5bd0e.png][]

思路：

一眼背包，把素数筛出来，把每个素数当成一个物品，做一遍完全背包就好了

状态设计：设dp\[i\]\[j\]为选到第 i 个素数，和**恰好** 为 j 的方案数

属性：count

状态转移：

决策：选or不选

dp\[i\]\[j\] = dp\[i-1\]\[j\] + dp\[i\]\[j-a\[i\]\]

小技巧：给数组降维，节约空间（&1）

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e3+10,mxv=8e4+10;
    int n,len=0,sum=0;
    int dp[2][mxv],vis[mxv],prime[mxn];
    void init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i,sum+=i;
            for(int j=1;prime[j]<=n/i;j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    void solve(){
        cin>>n;
        init(n);
        dp[0][0]=1;
        for(int i=1;i<=len;i++){
            for(int j=0;j<=sum;j++){
                if(j<prime[i]) dp[i&1][j]=dp[(i-1)&1][j];
                else dp[i&1][j]=dp[(i-1)&1][j]+dp[i&1][j-prime[i]];
            }
        }
        cout<<dp[len&1][n]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[P1832 A_B Problem_ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P1832
[f8ea0005c30446bcb14be83a58e5bd0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/71b7180b9f774ba299d9f3dc6924ad62.png

发表评论取消回复

表情：

评论列表（有 0 条评论，97人围观）

还没有评论，来说两句吧...

相关阅读

相关【DP完全背包】A+B Problem（再升级）

[P1832 A+B Problem（再升级） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1832 A_B Problem_ - _ _ _ _lu

迈不过友情╰/ 2024年03月30日 11:53/ 0 赞/ 98 阅读

相关背包DP | 完全背包问题

> 完全背包问题：有n种物品，每一件的物品重量为 w\[ i \]，价值为 c\[ i \]。现有一个容量为V的背包 (背包的最大承重为V)，问如何选取物品放入背包，使得背包内

小灰灰/ 2023年07月19日 10:34/ 0 赞/ 34 阅读

相关【DP】完全背包问题

问题描述现有n个物体和容量为V的背包，每个物体i都有对应的重量w\[i\]和价值v\[i\]，每个物体可以拿无数次，在所取物体总重量不超过V的情况下，能获得的最大

超、凢脫俗/ 2023年07月10日 08:29/ 0 赞/ 10 阅读

相关完全背包（经典dp）

完全背包时间限制：3000 ms | 内存限制：65535 KB 难度：4 描述直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可

柔光的暖阳◎/ 2022年10月01日 01:52/ 0 赞/ 190 阅读

相关完全背包

完全背包在背包九讲中有很详细的讲解，但是今天碰到题尝试了一下他给的算法，发现并不快，看了一下其他的代码，速度很快！题目链接http://hihocoder.com/prob

拼搏现实的明天。/ 2022年08月21日 02:16/ 0 赞/ 197 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 248 阅读

相关完全背包

完全背包和01背包的区别 > 01背包：有n个物品，每种物品只能被使用一次 > > 完全背包：有n个物品，每个物品可以被多次使用完全背包的递推公式可以由01背包的递推公

ゞ浴缸里的玫瑰/ 2022年06月08日 09:43/ 0 赞/ 196 阅读

相关完全背包

问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量

今天药忘吃喽~/ 2022年05月31日 01:05/ 0 赞/ 209 阅读

相关 DP(背包)

自用向 DP 背包 01背包 normal f i = m a x ( f i , f i − v + w ) f\_i = max(f

﹏ヽ暗。殇╰゛Y/ 2021年09月07日 06:08/ 0 赞/ 497 阅读

相关 hdu 2159 FATE(二维费用背包 DP完全背包) 题解

题解目录 1.题目 2.题意 3.思路 4.代码 1.题目

柔光的暖阳◎/ 2021年08月28日 12:42/ 0 赞/ 423 阅读