[DP][思维][×] codeforces 1183H Subsequences (hard version)

题目链接

题意:给定一个字符串S,长度为n≤100,然后定义一个操作是将S的一个含有L个字符的子序列看作一个字符串插入到一个无重复元素的set里,每次操作的cost是(n-L),然后问对于给定的k(k最大可取1e12),最少需要多少总cost才能使得set的元素个数达到k。难度2200分,有点虚高其实,不过还是不那么好想的。用先后顺序去重是关键idea。

做这种代码段但是考思维的小题还是挺有意思的。。。。

这题是mike出的,感觉挺经典那种。他有一个easy version是k≤100,这个要求的话就很松了,mike的题解直接用了一种及其暴力的方法:把每个subsequence当作一个点,相差一个字符的点之间连边建图,直接暴力跑bfs。。。这个肯定是个时间和空间复杂度都爆炸的算法,但是k≤100的时候很快就能搜到,只要及时跳出bfs就可以了。

这个H版本要求k最大可能是1e12,这就不能再那么操作了。首先写几个简单的样例就可以发现这个主要跟unique的子序列的长度和数量有关系,如果我们能求出来对应于某一长度j的unique子序列有多少个,那就可以解决这个问题了。这个就是一个引导方向,可以先试着设dp[i][j]表示以i为结尾的长度为j的子序列个数。状态定义好了之后考虑转移,按照大问题转化为小问题的思想,dp[i][j]表示的以i结尾的unique子序列,那么如果去掉s[i]之后这些子序列一定是互不相同的长度为j-1的子序列,数量没有多也没有少。所以现在就是要考虑怎么算出来前i-1个字符构成的子序列里面有多少个了。利用已经计算得得信息,这个一定是某些dp[pos][j-1]之和,但是有一种情况的是不同的pos对应的子串可能一样,所以这个题目最精彩的部分就来了,每次在相同的字符中选取最靠后的作为计算点。第一这样起码不会比选择前面的点坏,如果前面的点能凑成q个子序列那么后面的点凑成的相同长度的子序列只会多不会少,即不漏;第二这个就避免了重复计算的现象,不重不漏即为正确的dp转移。所以如果用\[lst[i][w]\]表示前i个字符里面字符为\[‘a’+w (w \in [0,25])\],可以写出来状态转移方程为

\[dp[i][j]=\sum_{w=0}^{25} dp[lst[i-1][w]][j-1]\]

至于lst显然很简单的一个dp就推出来了lst[i][j]=((int)(s[i]-‘a’)==j)?i:lst[i-1][j];

代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=1e2+5;
const ll ub=(ll)100000000000000;
ll lst[maxn][35];
ll dp[maxn][maxn];
char s[maxn];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;ll k;//error1
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<26;j++)
            lst[i][j]=((int)(s[i]-'a')==j)?i:lst[i-1][j];
    for(int i=1;i<=n;i++){
        dp[i][1]=1;
        for(int j=2;j<=i;j++){
            for(int w=0;w<26;w++){
                dp[i][j]+=dp[lst[i-1][w]][j-1];
                dp[i][j]=min(dp[i][j],ub);
            }
        }
    }
    ll ans=0,cnt;
    for(int j=n;j>=1;j--){
        cnt=0;
        for(int w=0;w<26;w++)
            cnt+=dp[lst[n][w]][j];
        if(k>cnt) k-=cnt,ans+=cnt*(n-j);
        else{
            cout<<ans+k*(n-j);
            return 0;
        }
    }
    if(k==1)
        cout<<ans+n;
    else
        cout<<-1;
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据