首页 > 代码库 > 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)