HDU3652(디지털 dp)

HDU 3652 문구: 1~n에 13으로 나뉘고 숫자에 13이 포함된 개수를 구하라

#include
#include
#include
#include
using namespace std;
int a[15],n,ans;
int dp[15][15][3];//dp[i][j][k]  i    ，%13 j，k=1       1，k=0        1，k=2       13 
int dfs(int pos,int m,int sta,int limit){
     
 if(pos==-1)  return (m==0&&sta==2);
 if(!limit&&dp[pos][m][sta]!=-1)  return dp[pos][m][sta];///     
 int up=limit?a[pos]:9;
 int tem=0;
 for(int i=0;i<=up;i++){
     
  if(sta==2)
  tem+=dfs(pos-1,(m*10+i)%13,2,limit&&(i==up));
  else if(sta==0)
  tem+=dfs(pos-1,(m*10+i)%13,i==1,limit&&(i==up));
  else if(sta==1){
     
   if(i==3)
   tem+=dfs(pos-1,(m*10+i)%13,2,limit&&(i==up));
   else if(i==1)
   tem+=dfs(pos-1,(m*10+i)%13,1,limit&&(i==up));
   else
   tem+=dfs(pos-1,(m*10+i)%13,0,limit&&(i==up));
  }
 } 
 if(!limit) dp[pos][m][sta]=tem;
 return tem;
}
int solve(int num){
     
 int pos=0;
 while(num){
     
  a[pos++]=num%10;
  num/=10;
 } 
 ans=dfs(pos-1,0,0,1);
}
int main(){
     
 while(scanf("%d",&n)!=EOF){
     
  memset(a,-1,sizeof(a));
  memset(dp,-1,sizeof(dp));
  ans=0;
  printf("%d
",solve(n));
 }
 return 0;
}