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.2cto.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;   
}