Cipher CodeForces - 156C（dp）

链接：http://codeforces.com/problemset/problem/156/C

题意：（太长，没仔细读，其实也看不懂）大概就是t组字符串， 对于每一组，在总的值不变的情况下问有多少中组成形式（值：a=1, b=2, c=3….， 并且范围在a-z）

解题思路：
对于长度为i 总值为j的字符串，它的组成形式数量等于长度为 i-1， 值为j-1至j-26的加和（j-x<0的情况除外）即dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]…dp[i-1][j-26]， 从dp[1][1]向上推就好了

注意：因为最多有10000组数据， 所以记录所有数据中的最大值，推一遍即可

代码：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define LL long long

using namespace std;

const int Max=210;
const int MOD=1e9+7;
char str[Max];
pair<int ,int > data[12000];
int dp[210][27110];
int main(){
    int n;
    scanf("%d", &n);
    int mem=0;
    int max11=0, max12=0;
    while(n--){
        scanf("%s", str);
        int len=strlen(str);
        int val=0;
        for(int a=0; a<len; a++){
            val+=str[a]-'a'+1;
        }
        max11=max(max11, len);
        max12=max(max12, val);
        data[mem++]=make_pair(len, val);
    }
    for(int a=1; a<=26; a++){
        dp[1][a]=1;
    }
    for(int i=2; i<=max11; i++){//len
        for(int j=i; j<=max12; j++){//val
            if(dp[i][j])continue;
            if(j-i<=25){
                dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%MOD;
            }
            else if(j-i>25){
                dp[i][j]=((dp[i][j-1]-dp[i-1][j-27]+MOD)%MOD+dp[i-1][j-1])%MOD;
            }
        }
    }
    for(int a=0; a<mem; a++)
        printf("%dn", ((dp[data[a].first][data[a].second]-1)+MOD)%MOD);
    return 0;
}

最后

以上就是魔幻老师为你收集整理的Cipher CodeForces - 156C（dp）的全部内容，希望文章能够帮你解决Cipher CodeForces - 156C（dp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。