1183 H. Subsequences (hard version)(dp)

传送门

如果想到了 $dp$ 的话,这题就不难了。

首先解决一个简单的问题,如何求出串 $a$ 有多少不同的子序列 $?$

定义 $f[i][j]$ 为以 $[1,i]$ 的长度为 $j$ 的子序列个数

$f[i][j]=f[i-1][j-1]+f[i-1][j]$ ,意思是选或者不选 $a_i$ 都是一种选择

但是有重复,考虑 $j<i$ 且 $a_j==a_i$ 时

$[1,j-1]$ 形成的子序列后面接上 $a_j$ 或者接上 $a_i$ 是等价的

所以真正的转移方程是

$f[i][j]=f[i-1][j-1]+f[i-1][j]-f[pre[a_i-'a']-1][j-1]$

也就是找到最近的一个满足条件的 $j$ ,然后去掉 $[1,j-1]$ 的方案数

那么这题就简单了..

这样处理出 $f[i][j]$ 数组去贪心即可得到解

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 109;
int n,k,pre[maxn],f[maxn][maxn],ans;
char a[maxn];
signed main()
{
    cin >> n >> k >> ( a+1 );
    f[0][0] = 1;
    for(int i=1;i<=n;i++)
    {
        f[i][0] = 1;
        for(int j=1;j<=i;j++)
        {
            f[i][j] += f[i-1][j-1]+f[i-1][j];
            if( pre[a[i]-'a'] )    f[i][j] -= f[pre[a[i]-'a']-1][j-1];
            if( f[i][j]>k )    f[i][j] = k;
        }
        pre[a[i]-'a'] = i;
    }
    for(int i=n;i>=0;i--)
    {
        int x = min( k,f[n][i] );
        k -= x;
        ans += x*(n-i);
    }
    if( k )    ans = -1;
    cout << ans;
}