[数据结构与算法]root p1919 题解

1919 -- 好序列

一.题目大意

就是给你一个序列，让你求所有能够划分成好字段的子序列

注意其中字段、子序列和好的序列

? ? ? ? 字段是指连续的一段子数组

? ? ? ? 子序列是指顺序不变，不必连续的一个子集

? ? ? ? 好的序列就是a[i],a[i+1]....a[i+a[i]],a[i]>=0时才有可能。。。

二.确定算法

这道题妥妥的DP（实际上一点都不妥，我就没想出来看的答案，）

好我们首先来从0开始一点一点想到DP（我想把自己的思路全部展现出来也很那，就不知道为甚么突然想到了DP，我尽量吧我的思维历程表现出来）

首先我先到暴力枚举所有可能的子序列，这当然最好想

? ? ? ? 我会时不时tab一下写一些和本题思路关系不大的做题习惯当做拓展

? ? ? ? 我们一般在做题时不要直奔正解，因为你可能想不到

? ? ? ? 一般的正解有两种来历，就是对暴力的剪枝油画(就比如2019cspj的第二题需要维护队列元素）和完全区别于质朴的思想，解决的根本就不是明面上题目所描述的模型，就像很多搜索题目，明明是数学题目，偏偏对一棵很虚的树遍历，对于这树的遍历，我这篇博客正在解释

? ? ? ? 好回到正解上来，如果大家是在刷题或者做项目时遇到不正解的问题，那么建议精益求精，找到或者搞懂正解为止

? ? ? ? 但如果是在考试中，与其花费老多时间想到正解（有可能还想不到或者错了（基本都是这样）），不如就花费很短的时间写个暴力骗点分，反而性价比更高；但如果其他题目都一点思路没有，那就不如把某一道有点苗头的题写个正解

行言归正传，发现暴力枚举妥妥的……超时

然后就各种线性,n^2,n^3,nlogn就往上挨个试

o(n)基本就不可能了，怎么可能子序列问题一边就扫号，人家还有其他特殊条件。。

o(nlogn)就是经典的二分或者排序加线性贪心，首先排序滚一边去 二分emm解又不是单调空间，没让你求最优质

n^3显然貌似似乎也许不一定不应该可以，毕竟三重循环图个啥（要真暴力还不是基层循环搞定的事儿）

上面的思路应该几分钟就过掉

接下来就是o(n^2)的算法，然后显然DP（呵呵由来）

由于n^2算法太多了，所以很难直接锁定，但是DP是其中比较大，也比较显眼的一个，所以先拿来开刀

设什么？下标什么意思？

设f[i]表示从i开始到最后有多少个子序列

怎么转移

由于是线性的，所以就考虑i前后的，发现只要i~j是一个好的子串，那么j往后的子序列个数就是乘法原理中的一个乘数，而剩下的就是该考虑的了

f[i]+=在不是好的序列中选择任意a[i]个数字作为f[i]的跟班，从j开始往后的就算原先的算

f[i]=f[j]*c[j-i-1][a[i]];

其中c[i][j]表示c的i中去j

枚举顺序

由于发现f[i]=f[j]。。。，j>i所以倒着循环

初始化

f[n+1]=1虽然n+1本质上没有意义，但由于需要他作为边界并不影响接下来的运算，就这样

实现：

f[n+1]=1;
	int ans=0;
	for(int i=n;i>=1;i--){
		if(a[i]<=0)continue;
		for(int j=i+a[i]+1;j<=n+1;j++){
			f[i]+=1ll*f[j]*c[j-i-1][a[i]]%mod;
			f[i]%=mod;
		} 
	} 
	for(int i=1;i<=n;i++){
		ans+=f[i];
		ans%=mod;
	}

三.算法细节

1.怎么实现c[i][j]

? ? ? ? 方法1：使用各种递推都行

? ? ? ? 方法2：我采用了二项式定理（说的人话一点就是杨辉三角）二重循环递推搞定：

void make_c(){
	for(int i=1;i<N;i++){
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;j++){
			c[i][j]=c[i-1][j]+c[i-1][j-1];
			c[i][j]%=mod;
		}
	}
}
	make_c();

2.十年OI一场空，不开longlong见祖宗，虽然最终的结果取余不会暴int但是中间有乘法运算就会暴

四.代码实现

#include<bits/stdc++.h>
using namespace std;

const int N=1005,mod=998244353;

long long c[N][N],a[N],f[N],n; 

void make_c(){
	for(int i=1;i<N;i++){
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;j++){
			c[i][j]=c[i-1][j]+c[i-1][j-1];
			c[i][j]%=mod;
		}
	}
}

int main(){
	make_c();
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	} 
	f[n+1]=1;
	int ans=0;
	for(int i=n;i>=1;i--){
		if(a[i]<=0)continue;
		for(int j=i+a[i]+1;j<=n+1;j++){
			f[i]+=1ll*f[j]*c[j-i-1][a[i]]%mod;
			f[i]%=mod;
		} 
	} 
	for(int i=1;i<=n;i++){
		ans+=f[i];
		ans%=mod;
	}
	printf("%d\n",ans);
	return 0;
}