Problem 178 「ステップ数」 †
45656を考えよう. 連続する2桁の数は全て差の絶対値が 1 である.
連続する2桁の数の差の絶対値が全て 1 である数をステップ数と呼ぶ.
パンデジタル数では0から9の各数が少なくとも 1 回出現する.
10^40未満の数でパンデジタル数かつステップ数であるものの数を答えよ.
何も考えない漸化式で一発です。
#include<stdio.h>
#include<iostream>
#include<string.h>
__int64 dp[41][1024][10];
int main(){
memset(dp,0,sizeof(dp));
int j=1;
for(int i=0;i<=9;i++){
dp[1][j][i]=1;
j*=2;
}
__int64 ans=0;
for(int i=2;i<=40;i++){
for(int j=1;j<=1023;j++){
int p=1;
for(int k=0;k<=9;k++){
if(k>0){
dp[i][j|(p/2)][k-1]+=dp[i-1][j][k];
}
if(k<9){
dp[i][j|(p*2)][k+1]+=dp[i-1][j][k];
}
p*=2;
}
}
for(int j=1;j<=9;j++){
ans+=dp[i][1023][j];
}
}
std::cout<<"ans="<<ans<<"\n";
}
最終更新:2016年01月09日 03:36