CF1183H Subsequences (hard version)

题意：

长度为n的字符串S，现在要找出k个不同的子序列，使得这些序列的总价值最低
一个序列的价值等于删去的字符长度（空串也算子序列）
1≤n≤100,1≤k≤10^12^

题解：

一看就是dp，我们先想想串a可以有多少不同的子序列
dp[i][j]表示前i个字符构造出来的长度为j的子序列数量
转移方程不难得到：
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]，（也就是选第i个和不选第i个）
但是这样做是存在重复的
比如satwt,按照上面的方法，st和at就会重复出现，那么怎么才能避免？因为t是重复的，我们只需要取最近的t就行
对于j<i且aj = = ai时，前j-1个字符形成的子序列后面接aj或者ai都是一样的，那么我干脆统一一下，接最近的
我们用pre[ai-'a']表示该字符出现上一次出现的位置
那么转移方程就是
dp [ i ] [ j ] = d p [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j ] - dp [ pre [ ai - 'a' ] - 1 ] [ j - 1 ]
找到最近的一个满足条件的j，然后去掉前j-1的方案数（删去重复数量）

代码：

#include<bits/stdc++.h>
typedef long long ll;
using name