[luogu] P1370 Charlie的云笔记序列 线性dp+离散化

前言

传送门 :

题意

给定 n , a [ ] n,a[] n,a[],对于 a [ l , r ] = { a l . . . . a r } a[l,r]=\{a_l....a_r\} a[l,r]={al​....ar​}

定义 F l , r = a [ l , r ] 中 不 同 子 序 列 的 数 量 F_{l,r}=a[l,r]中不同子序列的数量 Fl,r​=a[l,r]中不同子序列的数量

特别的 空串也算一种 (子序列不一定要连续

求 ∑ l = 1 n ∑ r = 1 n F [ l , r ] \sum_{l=1}^{n}\sum_{r=1}^{n}F[l,r] ∑l=1n​∑r=1n​F[l,r]

思路

这种题我们考虑 d p dp dp

状态表示 : f [ i ] f[i] f[i] 表示 ∑ j = 1 i F i j \sum_{j=1}^iF_{ij} ∑j=1i​Fij​

状态计算 : f [ i ] = f [ i − 1 ] + f [ i − 1 ] + 2 f[i]=f[i-1]+f[i-1]+2 f[i]=f[i−1]+f[i−1]+2

因为我们加入了 a [ i ] a[i] a[i],因此 f [ i ] f[i] f[i]又多了 f [ i ] f[i] f[i]种,同时 a [ i ] , { } a[i],\{\} a[i],{}也需要记录到答案中

又因为不能出现相同的子序列,因此我们需要考虑判重

对于 k < i kn; for(int i=1;i>a[i]; b[i] = a[i]; } sort(b+1,b+1+n); for(int i=1;i