[Acwing] 314.低买 LIS求解方案数

前言

传送门 :

思路

题目大致是, 求一段最长下降子序列 并且求 有多少方案数

我们设 d p [ i ] dp[i] dp[i] 表示转移到当前状态的方案数总和

显然 在每次转移的时候 我们都有 d p [ i ] + = d p [ j ] dp[i] += dp[j] dp[i]+=dp[j]

根据题意还可以得知 f [ i ] = = f [ j ] & & a [ i ] = = a [ j ] 情 况 下 d p [ j ] = 0 f[i]==f[j] \&\& a[i]==a[j]情况下 dp[j]=0 f[i]==f[j]&&a[i]==a[j]情况下dp[j]=0

下面考虑初始化什么时候 d p [ i ] = 1 dp[i]=1 dp[i]=1呢 ?

根据日常逻辑可知 本 身 到 本 身 本身到本身 本身到本身 属于一种转移 同理与 f [ i ] [ i ] = 1 f[i][i] = 1 f[i][i]=1

放到 L I S LIS LIS种,也就是 f [ i ] = 1 f[i]=1 f[i]=1,没有从其他地方转移过来,只从本身到本身进行转移的时候进行初始化

因此这题就变得简单了

(虽然写的时候并没有想出来怎么初始化,但是看了题解区的大佬还是清晰明了了)

Mycode

void solve()
{
	int n;cin>>n;
	for(int i=1;i>a[i];
	}
	
	int maxn = 0 ;
	int ans =0  ;
	
	for(int i=1;i