POJ 1850 Code && 1496 Word Index 组合数学

来源：http://poj.org/problem?id=1850 && http://poj.org/problem?id=1496

题意：两道题一样，一样的代码就可以过。就是说26个字母各对应一个整数，ab对应27，ac对应28.。。。这样对应下去，需要注意的是字符串必须是升序的，即后面的字符必须比前面的字符大。

思路：网上说是组合原理的应用，不过我没发现哪里用到了组合数学的知识，感觉就是一道普通的模拟题。想清楚就可以了。我做的时候是开了一个dp[27][27]的数组，dp[i][j]表示的是长度为i，以j开头的字符的序号，也就是对应的数字，并且用num[i][j]记录以长度为i，以j开头的字符有多少个。然后输入一个字符串，算就可以了。

代码：

//1850  1496#include <iostream>#include <cstdio>#include <string.h>#include <string>using namespace std;#define CLR(arr,val) memset(arr,val,sizeof(arr))typedef long long LL;const int N = 27;LL dp[N][N], num[N][N];bool fun(string ss){bool flag = true;for(int i = 0; i < ss.size() - 1; ++i){if(! (ss[i+1] > ss[i] )){  flag = false;  break;}}return flag;}void init(){CLR(dp,0);CLR(num,0);for(int i = 1; i < N; ++i){dp[1][i] = i;num[1][i] = 1;}for(int i = 2; i < N; ++i){for(int j = 1; j + i <= N; ++j){LL sum = 0;for(int k = 1; k + i - 1<= N; ++k)sum += num[i-1][k];if(j == 1)         dp[i][j] = dp[i-1][j] + sum;elsedp[i][j] = dp[i][j-1] + num[i][j-1];LL sum1 = 0;for(int k = j+1; k + i - 1 <= N; ++k)sum1 += num[i-1][k];num[i][j] = sum1;}}}int main(){//freopen("2.txt","w",stdout);init();string ss;while(cin>>ss){if(! fun(ss)){  printf("0\n");  continue;}  int len = ss.size();  int x = ss[0] - 'a' + 1;  LL id = dp[len][x];  for(int i = 1; i < len; ++i){     int y = ss[i] - 'a' + 1; x = ss[i-1] - 'a' + 1; LL sum = 0; for(int j = x + 1; j < y; ++j) sum += num[len - i][j]; id += sum;  }  printf("%lld\n",id);}return 0;}