【前缀和优化DP】ABC 222D

分手后的思念是犯贱 2024-03-17 19:19 112阅读 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 条评论，112人围观）

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

相关阅读

相关 Atcoder 前缀和优化DP Candies

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

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

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

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

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

相关 222

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

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

相关二维差分前缀和——cf1202D(好题）

直接枚举每个点作为左上角是可以做的，但是写起来较麻烦有一种较为简单的做法是对一列或一行统计贡献比如某一行的B存在的区间是L,R那么就有三种情况　　1.没有这样的区间

偏执的太偏执、/ 2023年10月11日 09:09/ 0 赞/ 55 阅读

相关优化MySQL前缀索引

目标 1. 明确前缀索引使用场景； 2. 掌握创建前缀索引的语法； 3. 掌握计算索引选择性的方法。 -------------------- 定义

素颜马尾好姑娘i/ 2023年07月02日 05:22/ 0 赞/ 59 阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关 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 赞/ 381 阅读