codeforces#1183H. Subsequences（字符串dp）

题目链接：

http://codeforces.com/contest/1183/problem/H

题意：

给出一个长度为$n$的字符串，得到$k$个子串，子串$s$的花费是$n-|s|$

计算最小花费

数据范围：

$1 \le n \le 100, 1 \le k \le 10^{12}$

分析：

dp依然还是那么神奇

定义$dp[i][j]$为考虑前$i$个字符，删除$j$个字符的方案数

首先$dp[i][j]=dp[i-1][j]+dp[i-1][j-1]$

前者为不保留第$i$个字符，后者为保留第$i$个字符，他们有重复的地方，即$dp[i-1][j-1]$的所有方案中，以$word[i]$结尾，长度为$i-j$的方案数

只需要减掉重复的方案数即可

ac代码：

#include<bits/stdc++.h>

#define ll long long

#define pa pair<int,int>

using namespace std;

const int maxn=100+10;

const ll mod=1e9+7;

ll dp[maxn][maxn];

char word[maxn];

int pre[30],n;

ll k,ans;

int main()

{

    scanf("%d %lld",&n,&k);

    scanf("%s",word+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];

            int zz=pre[word[i]-'a'];

            if(zz&&zz-i+j>=0)

                dp[i][j]-=dp[zz-1][zz-i+j];

            dp[i][j]=min(dp[i][j],k);

        }

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

    }

    for(int i=0;i<=n;i++)

    {

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

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

        if(k==0)break;

    }

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

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

    return 0;

}