首页 > 代码库 > Codeforces Round #396 (Div. 2)C. Mahmoud and a Message(dp)
Codeforces Round #396 (Div. 2)C. Mahmoud and a Message(dp)
题目链接:http://codeforces.com/problemset/problem/766/C
题意:给你一组小写字母组成的字符串,和26个数字,分别对应26位小写字母能够存在的字符串的最大长度。
要求:①:求出最多的划分方案
②:求出分配方案中,最长的子串长度
③:求出分配方案中,最少分成的子串数
思路:关于①:设置dp[i],dp[i]表示在第i个字符后面有一个横杠的方案数,从第i个往前枚举前一个横杠的位置j。
举个例子,有子串abc,当横杠断在a处,有一种方案,dp[1]=1;当横杠断在b处时,i=2,j=2表示分出子串“b”时方案数,此时dp[2]+=dp[1]=1;
i=2,j=1时表示分出子串“ab”,此时dp[2]+=dp[0]=1;那最后dp1[2]就等于2了;同理可以推出dp[3]=4。最后可以总结为当j~i段字符符合条件时,有dp[i]+=dp[j-1]+1.
②就不多说了,枚举过程中找出最长的子串就好了。
关于③,设置f[i],表示到i时的子串数,如果j~i段符合条件,那j~i就可以变为一个子串,f[i]可以变为f[j-1]+1;
#include<iostream> #include<algorithm> #include<string> using namespace std; const int MOD=1e9+7; const int inf=1<<30; const int N=1e3+5; int a[30],len; int dp[N],f[N]; string st; //每个小写字母都有一个数字a[i];表示这个字母能够存在于长度不超过a[i]的字符串内; bool judge(int l,int r){ int lim=r-l+1; for(int i=l;i<=r;i++){ if(a[st[i]-‘a‘]<lim) return false; } return true; } int main(){ int n,MAX=0; cin>>n>>st; st=" "+st; for(int i=0;i<26;i++){ cin>>a[i]; } //初始化 dp[0]=1; f[0]=0; for(int i=1;i<=n;i++){ f[i]=inf; for(int j=i;j>=1;j--){//j~i这一段字符串 if(judge(j,i)){ MAX=max(MAX,i-j+1); //printf("%d %d %d %d\n",i,j,dp1[i],dp1[j-1]); dp[i]=(dp[i]+dp[j-1])%MOD;//dp[i]表示在第i个字符后面有一个横杠的方案数,从第i个往前枚举前一个横杠的位置j f[i]=min(f[i],f[j-1]+1);//如果这一段合理,那么可以把j~i看成一个字串,那dp[i]的字串数也可以变形为dp[j-1]+1; } } } cout<<dp[n]<<endl; cout<<MAX<<endl; cout<<f[n]<<endl; }
Codeforces Round #396 (Div. 2)C. Mahmoud and a Message(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。