題意：

長度為n的字符串S，現在要找出k個不同的子序列，使得這些序列的總價值最低
一個序列的價值等于刪去的字符長度（空串也算子序列）
1≤n≤100,1≤k≤10¹²

題解：

一看就是dp，我們先想想串a可以有多少不同的子序列
dp[i][j]表示前i個字符構造出來的長度為j的子序列數量
轉移方程不難得到：
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]，（也就是選第i個和不選第i個）
但是這樣做是存在重復的
比如satwt,按照上面的方法，st和at就會重復出現，那么怎么才能避免？因為t是重復的，我們只需要取最近的t就行
對于j<i且aj = = ai時，前j-1個字符形成的子序列后面接aj或者ai都是一樣的，那么我干脆統一一下，接最近的
我們用pre[ai-‘a’]表示該字符出現上一次出現的位置
那么轉移方程就是
dp [ i ] [ j ] = d p [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j ] - dp [ pre [ ai - ‘a’ ] - 1 ] [ j - 1 ]
找到最近的一個滿足條件的j，然后去掉前j-1的方案數（刪去重復數量）

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1e4; int pre[maxn],dp[maxn][maxn],ans; string a; int main() {int n,k;cin>>n>>k>>a;for(int i=0;i<=n;i++){dp[i][0]=1;//空串 }for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i][j]+=dp[i-1][j-1]+dp[i-1][j];if(pre[a[i-1]-'a'])dp[i][j]-=dp[pre[a[i-1]-'a']-1][j-1];// if(dp[i][j]>k)dp[i][j]=k;}pre[a[i-1]-'a']=i;} for(int i=n;i>=0;i--){int x=min(k,dp[n][i]);k-=x;//價值ans+=x*(n-i); }if(k)cout<<-1;else cout<<ans; } /* a ad af*/

總結

以上是生活随笔為你收集整理的CF1183H Subsequences (hard version)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。