UVALIVE 4004

最近碼力略渣，敲題總是WA，考慮不全，還是要加強碼力

本題是一道組合數學統計問題

問的是給一個序列，求他在所有波浪序列中排名第幾

注意各種限制，各種特判.....

[cpp]
#include <cstdio>  
#include <cstring>  
#include <iostream>  
typedef long long ll; 
using namespace std; 
 
char s[1000]; 
ll dp[10][20][2]; 
int tot,a[20]; 
 
ll solve(int f,int llen,int dir){ 
    int i; 
    ll ans=1; 
    for(i=2;i<=18-llen;i++) 
        ans+=dp[f][i][dir]; 
    return ans; 
} 
 
ll dfs(int pos,int doing){ 
    if(pos==tot)return 0; 
    ll ans=0,i; 
    if(pos>=2)ans++; 
    if(pos==0){ 
        for(i=1;i<a[pos];i++){ 
            ans+=solve(i,pos,1); 
            ans+=solve(i,pos,0); 
            ans-=10; 
        } 
    } 
    else if(pos==1){ 
        for(i=1;i<a[pos];i++){ 
            if(i==a[pos-1])continue; 
            if(i>a[pos-1])ans+=solve(i,pos,1); 
            else ans+=solve(i,pos,0); 
            ans--; 
        } 
    } 
    else if(pos>=2){ 
        if(doing==0) i=a[pos-1]+1;else i=1; 
        for(;i<a[pos];i++){ 
            if(doing==0){ 
                ans+=solve(i,pos,1); 
            } 
            else ans+=solve(i,pos,0); 
        } 
    } 
    int next; 
    if(a[pos+1]>a[pos])next=0; 
    else next=1; 
    return ans+=dfs(pos+1,next); 
} 
void init(){ 
    int i,j,len; 
    memset(dp,0,sizeof(dp)); 
    for(i=1;i<9;i++) 
        dp[i][2][0]=9-i; 
    for(i=2;i<=9;i++) 
        dp[i][2][1]=i-1; 
    for(len=3;len<=18;len++){ 
        for(i=1;i<9;i++){ 
            for(j=i+1;j<=9;j++) 
                dp[i][len][0]+=dp[j][len-1][1]; 
        } 
        for(i=2;i<=9;i++){ 
            for(j=1;j<i;j++) 
                dp[i][len][1]+=dp[j][len-1][0]; 
        } 
    } 
} 
 
int main(){ 
//freopen("a.txt","r",stdin);  
//freopen("c.txt","w",stdout);  
    int t,T,len; 
    int i,j; 
    scanf("%d\n",&T); 
    init(); 
    for(t=1;t<=T;){ 
        gets(s); 
        tot=0; 
        len=strlen(s); 
        if(len==0)continue; 
        t++; 
        for(i=j=0;i<len;){ 
            a[j]=s[i]-'0'; 
            i++; 
            while(s[i]==' ')i++; 
            tot++; 
            j++; 
        } 
        cout<<dfs(0,-1)<<endl; 
    } 
    return 0; 
} 

#include <cstdio>
#include <cstring>
#include <iostream>
typedef long long ll;
using namespace std;

char s[1000];
ll dp[10][20][2];
int tot,a[20];

ll solve(int f,int llen,int dir){
    int i;
    ll ans=1;
    for(i=2;i<=18-llen;i++)
        ans+=dp[f][i][dir];
    return ans;
}

ll dfs(int pos,int doing){
    if(pos==tot)return 0;
    ll ans=0,i;
    if(pos>=2)ans++;
    if(pos==0){
        for(i=1;i<a[pos];i++){
            ans+=solve(i,pos,1);
            ans+=solve(i,pos,0);
            ans-=10;
        }
    }
    else if(pos==1){
        for(i=1;i<a[pos];i++){
            if(i==a[pos-1])continue;
            if(i>a[pos-1])ans+=solve(i,pos,1);
            else ans+=solve(i,pos,0);
            ans--;
        }
    }
    else if(pos>=2){
        if(doing==0) i=a[pos-1]+1;else i=1;
        for(;i<a[pos];i++){
            if(doing==0){
                ans+=solve(i,pos,1);
            }
            else ans+=solve(i,pos,0);
        }
    }
    int next;
    if(a[pos+1]>a[pos])next=0;
    else next=1;
    return ans+=dfs(pos+1,next);
}
void init(){
    int i,j,len;
    memset(dp,0,sizeof(dp));
    for(i=1;i<9;i++)
        dp[i][2][0]=9-i;
    for(i=2;i<=9;i++)
        dp[i][2][1]=i-1;
    for(len=3;len<=18;len++){
        for(i=1;i<9;i++){
            for(j=i+1;j<=9;j++)
                dp[i][len][0]+=dp[j][len-1][1];
        }
        for(i=2;i<=9;i++){
            for(j=1;j<i;j++)
                dp[i][len][1]+=dp[j][len-1][0];
        }
    }
}

int main(){
//freopen("a.txt","r",stdin);
//freopen("c.txt","w",stdout);
    int t,T,len;
    int i,j;
    scanf("%d\n",&T);
    init();
    for(t=1;t<=T;){
        gets(s);
        tot=0;
        len=strlen(s);
        if(len==0)continue;
        t++;
        for(i=j=0;i<len;){
            a[j]=s[i]-'0';
            i++;
            while(s[i]==' ')i++;
            tot++;
            j++;
        }
        cout<<dfs(0,-1)<<endl;
    }
    return 0;
}