P2362 围栏木桩

求每组数据的最长非递减子序列长度

t

及其方案数

c

。

长度是容易的，考虑方案求法。

定义 c[i]：以第

i

个木桩结尾的、长度为 f[i] 的非递减子序列的方案总数。

初始化：最开始只有一个木桩时，c[1] = 1

转移方程：若 a[j] ≤ a[i] 且 f[j] + 1 = f[i]，则 c[i] += c[j]

边界处理：后面如果一个位置 i 没有任何前驱能转移来，即第 i 个木桩前面没有比它低的木桩可以接上，c[1] = 1

这样实现：

CPP

for(int i=2;i<=n;i++)
{
	for(int j=1;j<i;j++)
	{
		if(f[j]+1==f[i] && a[j]<=a[i]) c[i]+=c[j];
	}
	if(c[i]==0) c[i]=1;
}

结果求法：所有 f[i] == ans 的 c[i] 累加得到总方案数 cnt

线性 dp 学习