dp好题CF1183H Subsequences (hard version)

CF1183H Subsequences (hard version)

考虑dp计算本质不同方案数
dp[i][j]表示在前i个字符中，长度为j的本质不同的子串数
跑pre[i]表示de字母出现的上一个位置

pre数组我属实没有想到，看了题解之后觉得这个很妙
pre数组的作用是为了除去和原来本质相同的字符串
转移的时候减掉就可以了

如果i这个点有对应的pre[i]那么dp[i][j]-=dp[pre[i]-1][j-1]即可
剩下的正常转移即可 dp[i][j]=dp[i-1][j]+dp[i-1][j-1] 不动的情况+算上i这个点 的方案数

算出来对应长度能有的本质不同方案数可以干什么呢?
由于花费是删掉的字符数量，串长越长越优
考虑贪心，从最长的长度从头开始减即可

结果分三类考虑:
1.还剩>1的字符串数要凑 但不够了,输出-1即可
2.还剩1个字符串数,我们发现还有空串的情况,ans+=n,再输出
3.一个不剩了,结果就是ans

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=1e3+10;

ll read() {
	
	ll x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57) {
		if(ch=='-') f=-1;
		ch=getchar(); 
	}
	while(ch>=48&&ch<=57) {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
	
}

char s[N];
ll n,k,ans=0,dp[N][N],pre[N];

int main() {
	
	n=read();
	k=read();
	cin>>(s+1);
	for(ll i=1;i<=n;i++) {
		
		for(ll j=i+1;j<=n;j++) {
			
			if(s[i]==s[j]) pre[j]=i;
			
		}
		
	}
	
	for(ll i=0;i<=n;i++) dp[i][0]=1;
	for(ll i=1;i<=n;i++) {
		
		for(ll j=1;j<=i;j++) {
			
			dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
			if(pre[i]) dp[i][j]-=dp[pre[i]-1][j-1];
			
		}
		
	}
	
	for(ll i=n;i>=1&&k;i--) {
		
		ans+=min(dp[n][i],k)*(n-i);
		k=max(0ll,k-dp[n][i]);
		
	}
	if(k>1) printf("-1\n");
	else if(k==1) printf("%lld\n",ans+n);
	else printf("%lld\n",ans);
	
	return 0;
}

原文地址：http://www.cnblogs.com/Diamondan/p/16900211.html