codeforces 1183H 动态规划

传送门：https://codeforces.com/contest/1183/problem/H

题意：

给你一串长度为n的字符串，你需要寻找出他的最长的前k个子串，问你得到这些子串需要减少的字符个数之和是多少，easy版本的k是100，hard版本的k是1e12。

题解：

hard版本题解：

dp[i][j]表示前i个字符中选择了j个的子串数目

如果前面有出现过的字符呢？比如 aba 算到第二个a的时候 把ab 删掉 和 把 ba删掉 得到同一种结果

因此，对于XYYX 这种形式的我们把第一个X之前出现过的种数去掉，就可以避免多算的情况了

这里我们用一个pre数组来记录第一个X出现的位置

代码：

#include <set>

#include <map>

#include <cmath>

#include <cstdio>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const int maxn = 3e5 + 5;

const int INF = 0x3f3f3f3f;

LL dp[1005][1005];

char a[maxn];

int pre[1005];

int main() {

#ifndef ONLINE_JUDGE

    FIN

#endif

    IO;

    int n;

    LL k;

    scanf("%d%lld%s", &n, &k, a + 1);

    dp[0][0] = 1;

    for(int i = 1; i <= n; i++) {

        dp[i][0] = 1;

        for(int j = 1; j <= i; j++) {

            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]);

            if(pre[a[i] - 'a']) dp[i][j] -= dp[pre[a[i] - 'a'] - 1][j - 1];

            if(dp[i][j] > k) dp[i][j] = k;

        }

        pre[a[i] - 'a'] = i;

    }

    LL ans = 0;

    for(int i = n; i >= 0; i--) {

        ans += min(dp[n][i], k) * (n - i);

        k -= dp[n][i];

        if(k <= 0) break;

    }

    if(k > 0) printf("-1\n");

    else printf("%lld\n", ans);

    return 0;

}