糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 1850 Code 动态规划

思路：

f[ch][len] = { 有多少个以 ch 开头，长度为 len 的字符串 }


#include <stdio.h>

__int64 dp[16][32], sum[16], ans;

int main()
{
    int i, j, len;
    char str[16];

    freopen("e:\\test\\in.txt", "r", stdin);

    for (i = 0; i < 26; i++)
        dp[0][i] = 1;
    for (i = 1; i < 10; i++) {
        for (j = 25 - i; j >= 0; j--) {
            dp[i][j] += dp[i][j + 1];
            dp[i][j] += dp[i - 1][j + 1];
        }
    }
    for (i = 0; i < 10; i++) 
        for (j = 0; j < 26; j++)
            sum[i] += dp[i][j];

    scanf("%s", str);
    for (len = 0; str[len]; len++)
        ans += sum[len];
    ans -= sum[len - 1];
    j = 0;
    for (i = len - 1; i >= 0; i--) {
        while (j < str[len - 1 - i] - 'a') {
            ans += dp[i][j];
            j++;
        }
        j++;
    }
    for (i = 0; i < len - 1; i++)
        if (str[i] >= str[i + 1])
            ans = -1;
    printf("%I64d\n", ans + 1);

    return 0;
}

posted on 2010-04-22 21:52 糯米 阅读(340) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理