【前缀和优化DP】ABC 222D

分手后的思念是犯贱 2024-03-17 19:19 42阅读 0赞

**虽然很简单，但是统一一下板子，以防写错**

[D - Between Two Arrays (atcoder.jp)][D - Between Two Arrays _atcoder.jp]

题意：

![a38cf57a652c401fa967bb704c180a99.png][]

思路：

直接DP即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e3+10;
    const int mxe=3e3+10;
    const int Inf=0x3f3f3f3f;
    const int mod=998244353;
    
    int N;
    int a[mxn],b[mxn],c[mxn];
    int pre[mxn];
    int dp[mxn][mxn];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=N;i++) cin>>b[i];
    	for(int i=a[1];i<=b[1];i++){
    		dp[1][i]=(dp[1][i]+1)%mod;
    	}
    	for(int i=2;i<=N;i++){
    		pre[0]=dp[i-1][0];
    		for(int k=1;k<=3000;k++){
    			pre[k]=(pre[k-1]+dp[i-1][k])%mod;
    		}
    		for(int j=1;j<=3000;j++){
    			if(j<a[i]||j>b[i]) continue;
    			dp[i][j]=(dp[i][j]+pre[j]-pre[max(j,a[i-1])])%mod;
    		}
    	}
    	int ans=0;
    	for(int i=a[N];i<=b[N];i++) ans=(ans+dp[N][i])%mod;
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[D - Between Two Arrays _atcoder.jp]: https://atcoder.jp/contests/abc222/tasks/abc222_d
[a38cf57a652c401fa967bb704c180a99.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f88abba322544d9f9626f47f69d9280c.png

发表评论取消回复

表情：

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

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

相关阅读

相关 Atcoder 前缀和优化DP Candies

[Candies - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][Candies - _ _ _ _luogu.com.cn] 题意： ![7cc590

深碍√TFBOYSˉ_/ 2024年03月30日 09:26/ 0 赞/ 21 阅读

相关【前缀和优化DP】ABC 222D

虽然很简单，但是统一一下板子，以防写错 [D - Between Two Arrays (atcoder.jp)][D - Between Two Arrays _atcod

分手后的思念是犯贱/ 2024年03月17日 19:19/ 0 赞/ 43 阅读

相关 222

\ /etc/services:\ $Id: services,v 1.48 2009/11/11 14:32:31 ovasik Exp $\\ Network servic

清疚/ 2024年02月17日 23:10/ 0 赞/ 15 阅读

相关 D. Non-zero Segments----前缀和

一维前缀和： sum\[0\] = 0; sum\[i\] = sum\[i-1\] + a

古城微笑少年丶/ 2022年11月19日 07:38/ 0 赞/ 105 阅读

相关 18927 前缀和

题目描述前缀和是一种重要的预处理方法，能极大地降低查询序列区间和的时间复杂度。现在一个序列中有n个整数，下标从1…n。有m个查询，每个查询给出一个区间的左右

蔚落/ 2022年11月13日 04:11/ 0 赞/ 143 阅读

相关 Leetcode——前缀和

[题目直通车][Link 1] 运用数学思想左边的和 = 总和 - 当前索引的值-右边的和题目要求两边相等，也就是左边的和 = 右边的和因此公式变成左

分手后的思念是犯贱/ 2022年10月24日 01:42/ 0 赞/ 141 阅读

相关树形DP+前缀和优化 nkoj P3723

<table> <tbody> <tr> <td> <table> <tbody> <tr> <td>评测

绝地灬酷狼/ 2021年10月18日 12:36/ 0 赞/ 214 阅读

相关 D. Irreducible Anagrams (思维、前缀和、构造)

[题目][Link 1] 题意：一个字符串如果只是其中字符顺序被打乱则称其和原字符串相互为字谜。对于两个互为字谜的字符串，两个字符串按相同的位置分割开成为n(n>=2)个

偏执的太偏执、/ 2021年07月16日 22:40/ 0 赞/ 341 阅读

相关 1372 D. Omkar and Circle (思维、前缀和)

[题目][Link 1] 思路：对于为n的奇数，可以进行(n-1)/2次让一个数取代相邻两数操作，直到最后只剩下一个数，其实每次操作就是删掉了一个数，那要如何让删除后的总

素颜马尾好姑娘i/ 2021年07月16日 19:14/ 0 赞/ 343 阅读

相关 1358 - D. The Best Vacation (贪心+二分+前缀和)

[题目][Link 1] 思路：贪心一下，要使拥抱次数最多必然是以每一个月的末尾为最后一天时，假设b(n-3) b(n-2) b(n-1) b(n) …c(1) c(2)

爱被打了一巴掌/ 2021年07月16日 11:43/ 0 赞/ 306 阅读