首页 > 代码库 > POJ 1850

POJ 1850

逐位确定其上可填的字母,组合数学题。

注意:当不符合规则时,要求输出0;

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string.h>using namespace std;int M[30][30];char s[30];int num[30];void initial(){	memset(M,0,sizeof(M));	for(int i=0;i<=26;i++)	M[i][0]=1;	for(int i=1;i<=26;i++){		for(int j=1;j<=i;j++){			if(j==1){				M[i][j]=i;			}			else {				M[i][j]=M[i][j-1]*(i-j+1)/j;			}		}	}}int main(){	initial();	while(scanf("%s",s)!=EOF){		int len=strlen(s);		for(int i=1;i<=len;i++)		num[i]=s[i-1]-‘a‘+1;		num[0]=0;		bool flag=true;		for(int i=1;i<=len;i++)		if(num[i]<=num[i-1]){			flag=false;			break;		}		if(!flag){			printf("0\n");			continue;		}		int pos=0;		for(int i=1;i<len;i++)		pos+=M[26][i];		for(int i=1;i<=len;i++){			for(int k=num[i-1]+1;k<num[i];k++){				pos+=(M[26-k][len-i]);			}		}		printf("%d\n",pos+1);	}	return 0;}

  

POJ 1850