当前位置: 代码迷 >> 综合 >> HDU3653-数位DP
  详细解决方案

HDU3653-数位DP

热度:71   发布时间:2024-01-18 01:08:05.0
//数位DP
//判断1-n中有多少个数字含有13且是13的倍数
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std ;int n ;
int len ;
int bit[20] ;
int dp[20][20][3] ;
//dp[pos][mod][st]
//pos:数位
//mod:余数
//st:  st==0末尾不是1
//     st==1末尾是1
//     st==2含有13void init(int n) //初始化函数,把各个数位拆开放在数组里
{memset(dp , -1 , sizeof(dp)) ;len = 0 ;while(n){bit[++ len] = n % 10 ;n /= 10 ;}
}
int DP(int pos , int mod , int st , int flag)//flag用来记录上限
{if(pos == 0) return (st == 2 && mod == 0) ;if(flag && dp[pos][mod][st] != -1) return dp[pos][mod][st] ;int ans = 0;int x = flag ? 9 : bit[pos] ;//假设该位是2,下一位是3,如果现在算到该位为1,那么下一位是能取到9的,如果该位为2,下一位只能取到3for(int i = 0 ; i <= x ; i ++){int temp = (mod * 10 + i) % 13 ;//看是否能整除13if((st == 2) || (st == 1 && i == 3))ans += DP(pos - 1 , temp , 2 , flag || i < x) ;else if(i == 1) ans += DP(pos - 1 , temp , 1 , flag || i < x) ;else ans += DP(pos - 1 , temp , 0 , flag || i < x) ;//在最开始,取出的num是最高位,所以如果i比num小,那么i的下一位都可以到达9,而i==num了,最大能到达的就只有,bit[pos-1]}if(flag) dp[pos][mod][st] = ans ;return ans ;
}
int main()
{while(scanf("%d" , &n) != EOF){init(n) ;cout << DP(len , 0 , 0 , 0) << endl ;}return 0 ;
}

  相关解决方案