UVALIVE 4004 (一)

最近码力略渣，敲题总是WA，考虑不全，还是要加强码力

本题是一道组合数学统计问题

问的是给一个序列，求他在所有波浪序列中排名第几

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

[cpp]
#include
#include
#include
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 ans+=solve(i,pos,1);
ans+=solve(i,pos,0);
ans-=10;
}
}
else if(pos==1){
for(i=1;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 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 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 a[j]=s[i]-'0';
i++;
while(s[i]==' ')i++;
tot++;
j++;
}
cout< }
return 0;
}

#include
#include
#include
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 ans+=solve(i,pos,1);
ans+=solve(i,pos,0);
ans-=10;
}
}
else if(pos==1){
for(i=1;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 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 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;
in