1183 H. Subsequences (hard version)(dp)

传送门

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

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

定义为以的长度为的子序列个数

,意思是选或者不选都是一种选择

但是有重复,考虑且时

形成的子序列后面接上或者接上是等价的

所以真正的转移方程是

也就是找到最近的一个满足条件的,然后去掉的方案数

那么这题就简单了..

这样处理出数组去贪心即可得到解

#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;
}