Poj 1496 Word Index & Poj 1850 Code (计数组合数)

水深无声 2022-08-25 13:55 48阅读 0赞

两题除了字符串长度不同之外没有区别。

题意：字符串的合法排序规则为：长度小的靠前，同长度则按字典序，每个字符串内部字母都是升序的。

思路：因为满足字符串内部也都是升序的，所以对于长度为L的字符串，满足条件的个数便是从26个字母中选出L个，即C\[26\]\[L\]。借此统计比它短的部分，等长度的串枚举解决。

本题方法很多，可以动态规划：http://blog.sina.com.cn/s/blog\_6635898a0100lkac.html 或者暴力： http://www.cnblogs.com/illuminator/archive/2013/03/22/POJ1496.html

#include <cstdio>
    #include <cstring>
    
    int c[30][30];
    
    void Init ()
    {
    	for (int i=0;i<=26;i++)
    	{
    		c[i][0]=c[i][i]=1;
    		for (int j=1;j<i;j++)
    			c[i][j]=c[i-1][j]+c[i-1][j-1];
    	}
    }
    
    int main ()
    {
        Init();
    	char str[20];
    	while (~scanf("%s",str))
    	{
    		bool flag=false;
    		int len=strlen(str),i;
    		for (i=0;i<len-1;i++)
    			if (str[i]>=str[i+1])
    				flag=true;
    		if (flag)
    		{
    			printf("0\n");
    			continue;
    		}
    		int sum=0;
    		for (i=1;i<len;i++)
    			sum+=c[26][i];
    		for (i=0;i<len;i++)
    		{
    			char ch;
    			if (i==0) 
    				ch='a';
    			else 
    				ch=str[i-1]+1;
    			for (char j=ch;j<str[i];j++)
                     sum+=c['z'-j][len-1-i];
    		}
    		printf("%d\n",sum+1);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，48人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 1737-Connected Graph【计数DP】

求 N 个节点的无向连通图有多少个，节点有标号，编号为1~N。例如下列图示，三个节点的无向连通图共4个。 ![1737\_1.jpg][1737_1.jpg] 输入格式

谁践踏了优雅/ 2023年08月17日 15:46/ 0 赞/ 8 阅读

相关 Poj 1496 Word Index & Poj 1850 Code (计数组合数)

两题除了字符串长度不同之外没有区别。题意：字符串的合法排序规则为：长度小的靠前，同长度则按字典序，每个字符串内部字母都是升序的。思路：因为满足字符串内部也都是升序的，所

水深无声/ 2022年08月25日 13:55/ 0 赞/ 49 阅读

相关【POJ】：POJ 3984

题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984] 题目解析：这题算是搜索里面的简单题了吧

Myth丶恋晨/ 2022年08月23日 04:50/ 0 赞/ 220 阅读

相关 poj1942求组合数

就是一求组合数的问题。 include <iostream> include <algorithm> using namespac

我会带着你远行/ 2022年08月22日 15:23/ 0 赞/ 195 阅读

相关 POJ 1850 Code/POJ 1496 Word Index（组合数学-字母串序号）

Code <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

布满荆棘的人生/ 2022年07月10日 04:30/ 0 赞/ 130 阅读

相关质因数计数公式 POJ 2992 Divisors

Divisors [http://poj.org/problem?id=2992][http_poj.org_problem_id_2992] Time L

た入场券/ 2022年06月04日 08:54/ 0 赞/ 123 阅读

相关 poj1321+poj2251

poj1321代码实现（dfs）： include <iostream> include <string.h> using namespace std

心已赠人/ 2022年05月30日 04:08/ 0 赞/ 206 阅读

相关 poj1850（组合数）

题目链接：http://poj.org/problem;jsessionid=B0D9A01EC0F1043088A37454B6CED469?id=1850 题意：给字符串

以你之姓@/ 2021年12月21日 01:05/ 0 赞/ 237 阅读

相关 poj1037（计数dp）

题意：给定n个数字，规定一种 cute 排序：序列中的数字大小为严格的波浪形，即 a\[0\] > a\[1\] < a\[2\] > a\[3\] < .... 或者 a\

àì夳堔傛蜴生んèń/ 2021年11月29日 14:42/ 0 赞/ 343 阅读

相关 POJ - 1737 Connected Graph（计数dp）

题意：求n个点组成的连通图的种数。分析：经典DP。详见《算法竞赛进阶指南》P337。代码： include <cstdio> includ

一时失言乱红尘/ 2021年11月29日 05:26/ 0 赞/ 245 阅读