POJ 1850 Code(组合数学）

题目链接

这个题目的组合解法，太巧妙了。长度为n的方案数总和为C(26,n)，我竟没有发现。。然后+长度和字符串相等的时候的情况，第一位默认，以后默认为前一位+1，这样才能保证递增特性。

网上还有DP解法，智商拙计啊。。。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int c[27][27]; 6 int main() 7 { 8 int i,j,k,len; 9 long long ans = 0; 10 char str[101]; 11 for(i = 0;i <= 26;i ++) 12 c[i][0] = 1; 13 for(i = 1;i <= 26;i ++) 14 { 15 for(j = 1;j <= i;j ++) 16 c[i][j] = c[i-1][j-1] + c[i-1][j]; 17 } 18 scanf("%s",str); 19 len = strlen(str); 20 for(i = 0;i < len-1;i ++) 21 { 22 if(str[i] >= str[i+1]) 23 { 24 printf("0\n"); 25 return 0; 26 } 27 } 28 for(i = 1;i <= len-1;++ i) 29 { 30 ans += c[26][i]; 31 } 32 for(i = 0;i < len;++ i) 33 { 34 if(i == 0) 35 j = 'a'; 36 else 37 j = str[i-1] + 1; 38 for(;j < str[i];j ++) 39 { 40 ans += c['z'-j][len-i-1]; 41 } 42 } 43 printf("%lld\n",ans+1); 44 return 0; 45 }

 

转载于:https://www.cnblogs.com/naix-x/archive/2013/01/22/2871491.html

总结

以上是生活随笔为你收集整理的POJ 1850 Code(组合数学）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。