F - Knapsack for All Segments（01背包）

Myth丶恋晨 2023-07-18 02:41 11阅读 0赞

[F - Knapsack for All Segments][]

题意：一个长度为n的数组，求任意\[ L,R \]区间和为S的总数。

题解：01背包

dp\[N\]代表前i个数中和为N的数量  
每次dp\[0\]+=1，我们01背包板子循环到第i个物品求的是前i个物品和为N的数量，并没有  
\[2,i\]、\[3，i\]、\[4，i\]、…、\[i，i\]这些情况，少了i-1种情况答案肯定不对，所以我们只需要把dp\[0\]赋值为 1 + （i-1） 原始就为1，再加上少的i-1中情况。

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    const ll maxn=1e4+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    const ll mod=998244353;
    void io(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
    ll a[maxn],dp[maxn];
    int main()
    { 
    	io();
    	ll n,k;
    	cin>>n>>k;
    	for(int i=1;i<=n;i++) cin>>a[i]; 
    	ll ans=0; 
    	for(int i=1;i<=n;i++)
    	{ 
    		dp[0]+=1;//[2,i]、[3，i]、[4，i]、...、[i，i]
    		for(int j=k;j>=a[i];j--)
    			dp[j]=(dp[j]+dp[j-a[i]])%mod;
    		ans=(ans+dp[k])%mod;//前i个数的和为K的数量
    	}
    	cout<<ans<<endl;
    	return 0;
    }

[F - Knapsack for All Segments]: https://atcoder.jp/contests/abc159/tasks/abc159_f

发表评论取消回复

表情：

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

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

相关阅读

相关【经典算法题】背包问题（Knapsack Problem）

说明假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物品，假设是水果好了，水果的编号、单价与重量如下所示： <table> <thead

布满荆棘的人生/ 2023年10月14日 13:37/ 0 赞/ 42 阅读

相关 F - Knapsack for All Segments（01背包）

[F - Knapsack for All Segments][] 题意：一个长度为n的数组，求任意\[ L,R \]区间和为S的总数。题解：01背包 dp\[N\]代

Myth丶恋晨/ 2023年07月18日 02:41/ 0 赞/ 12 阅读

相关 01背包

01背包题目描述给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个输入的第一行包

爱被打了一巴掌/ 2022年12月04日 04:27/ 0 赞/ 177 阅读

相关背包问题-背包01-苹果

package 动态规划.背包01; import java.util.Scanner; public class 苹果 \{ static class

野性酷女/ 2022年07月12日 12:12/ 0 赞/ 256 阅读

相关 01背包,完全背包

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

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

相关 01背包

> 题目：有一个背包，体积为m，现在给你n个石头，每个石头都有价值和体积，问这个背包可以装下多大价值的石头。 > > 输入： > 第一行两个整数n，m，分别代表石头的个数

╰半夏微凉°/ 2022年06月08日 09:37/ 0 赞/ 208 阅读

相关 01背包

01背包 > 且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ > > 小Ho现在手上有M张奖券，而奖品区有N

水深无声/ 2022年05月31日 06:29/ 0 赞/ 642 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 368 阅读

相关 FZU - 2214 Knapsack problem（0 1 背包++）

[FZU - 2214 Knapsack problem][] Accept: 837 Submit: 3249 Time Limit: 3000 mSec Memor

旧城等待，/ 2022年05月26日 01:36/ 0 赞/ 115 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 303 阅读