首页 > 代码库 > zoj 1342 - Word Index
zoj 1342 - Word Index
题目:有一个单词表a,..,z,ab,..,yz,...vwxyz,给你一个单词,输出对应的编号。
分析:dp,数学。利用递推统计计数即可知道位置。
状态:F(l,s)代表长度为l的起始为s的元素的个数;
阶段:长度 { 逆向向前拼 };
转移:F(l,s)= sum(F(l-1,t)) { 其中,s < t };
说明:应该可以用数学推出公式的(2011-09-19 11:04)。
#include <stdio.h> #include <string.h> int Count[ 6 ][ 27 ]; char Data[ 6 ]; void makelist( void ) { int i,j,k; memset( Count, 0, sizeof( Count ) ); for ( i = 1 ; i <= 26 ; ++ i ) Count[ 1 ][ i ] = 1; for ( i = 2 ; i <= 5 ; ++ i ) { for ( j = 1 ; j <= 26 ; ++ j ) for ( k = j+1 ; k <= 26 ; ++ k ) Count[ i ][ j ] += Count[ i-1 ][ k ]; } } int calc( int s, int v, int L ) { int i,Sum = 0; for ( i = s+1 ; i < v ; ++ i ) Sum += Count[ L ][ i ]; return Sum; } int number( char ch ) { return ch-'a'+1; } bool legal( int L ) { for ( int i = 1 ; i < L ; ++ i ) if ( Data[ i ] <= Data[ i-1 ] ) return false; return true; } int main() { makelist(); while ( ~scanf("%s",&Data[ 1 ]) ) { int Len = strlen( &Data[ 1 ] ); if ( legal( Len ) ) { int i,j,Sum = 1; Data[ 0 ] = 'a'-2;//补充循环边界 for ( i = 1 ; i <= Len ; ++ i ) Sum += calc( number( Data[ i-1 ] ), number( Data[ i ] ), Len-i+1 ); for ( i = 1 ; i < Len ; ++ i ) for ( j = 1 ; j <= 26 ; ++ j ) Sum += Count[ i ][ j ]; printf("%d\n",Sum); }else printf("0\n"); } return 0; }
zoj 1342 - Word Index
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。