POJ 1850 Code

坐标都弄得我头晕。我先打表把以某字母开头长度为i的方案数都预先存储。然后再从输入的字符串里面分解：

假设为 cdvx字符串，把长度为1,2,3的所有方案数相加，然后从做到右来分析，第一个字符c,第一个字符最小必须为a,把a,b开头长度为4的方案数加起来；第二个字符最小必须为‘c’+1也就是d，所以这个不管;v这个位置必须大于'd',所以又把‘e’~‘u’开头长度为2的方案数加起来，最后一位一样的做法。

到这里应该知道解题的方法了，有人说这是杨辉三角，把打表的结果输出来一看真的是杨辉三角，但是做法是一样的。

代码：

[cpp]
#include<iostream>
using namespace std;
int dp[30][30],cnt[30]; //dp为以某字符开头长度为i的方案数，cnt为长度为i的所有方案数。
int main()
{
    int i,j,k,sum,temp;
    for( i=1;i<=26&&(dp[1][i]=1);i++);
    cnt[1]=26;
    for( i=2,sum=26;i<=26;i++){
         temp=0;
         for( j=1;j<=27-i;j++){
              sum-=dp[i-1][j];
              dp[i][j]=sum;
              temp+=sum;
         } www.zzzyk.com
         sum=temp; cnt[i]=sum;
    }

    char str[15];

    while( scanf("%s",str)!=EOF){
           sum=0;
           bool flag=true;
           int len=strlen(str);
           for( i=1;i<len;i++){
                if( str[i]-str[i-1]<=0){ //判断有没有降序的情况
                    flag=false; break;}
                else sum+=cnt[i];
           }
           if( flag){
           for( i=0;i<len;i++){   //按分析解题
                j=( i==0? 1:str[i-1]-'a'+2 );
                for( ;j<=str[i]-'a';j++)
                     sum+=dp[len-i][j];
           }
           printf("%d\n",sum+1);
           }
           else
            printf("0\n");
    }
    return 0;
}

补充：软件开发 , C++ ,