51nod 2180 争渡

争渡 原题链接

常记溪亭日暮，沉醉不知归路。兴尽晚回舟，误入藕花深处。争渡，争渡，惊起一滩鸥鹭。 ——李清照《如梦令·常记溪亭日暮》

给出线段上界和下界，要在严格递增地在区间内选数，问到最后一条线段的方案数。

见上图，第 \(i\) 条线段 \(j\) 点的方案数为 \(i-1\) 条线段的 \(j-1\) 到 \(l[i-1]\) 的方案数的总和。

所以我们可以得到设状态为 dp[i][j] 前 i 条线段点数为 j 的方案数，我们也可以得到动态转移方程 \(dp[i][j]=\sum_{k=l[i-1]}^{j-1} dp[i-1][k]\)

但是这样做的时间复杂度有点高，那如何优化呢。

考虑使用前缀和优化，我们用 sum 数组将上方的求和储存起来，这样就不用每次都需要重复计算一次了。

总复杂度为 \(O(n\times M)\)，\(M\) 为值域。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int mod=998244353;
int n; 
int l[N],r[N];
int dp[205][N];
int sum[N];

int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	
	for(int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
	} 
	
	for(int i=l[1];i<=r[1];i++){//初始化方案数 
		dp[1][i]=1;
	}
	
	for(int i=0;i<=N;i++){//求前缀和 
		sum[i]=(sum[i-1]+dp[1][i])%mod;
	} 
	
	for(int i=2;i<=n;i++){//从第二个开始 
		for(int j=l[i];j<=r[i];j++){//O(1) 获取方案数 
			dp[i][j]=sum[j-1];
		}
		sum[0]=0;//初始化，重置数组 
		for(int j=0;j<=N;j++){//再次求前缀和 
			sum[j]=(sum[j-1]+dp[i][j])%mod;
		} 
	}
	long long ans=0;
	for(int i=l[n];i<=r[n];i++){//统计方案数 
		ans=(ans+dp[n][i])%mod;
	}
	cout<<ans;
    return 0;
}