程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu3652 B-number(數位dp+dfs)

hdu3652 B-number(數位dp+dfs)

編輯:C++入門知識

hdu3652 B-number(數位dp+dfs)


B-number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3376 Accepted Submission(s): 1891



Problem Description A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string 13 and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
Input Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
Output Print each answer in a single line.
Sample Input
13
100
200
1000

Sample Output
1
1
2
2

Author wqb0039
Source 2010 Asia Regional Chengdu Site —— Online Contest
題意:找出1~n有多少個數既含有13又能被13整除。 分析:記憶化搜索配合數位dp求解。
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define ll long long
#define CL(a) memset(a,0,sizeof(a))

int dp[15][15][3],s[15];//dp[i][j][k],i表示位數,j表示余數,k表示末尾是1、末尾不是1、含有13.

int dfs(int pos, int mod, int have, int lim)//前三個數對應數組dp,lim表示上限
{
    int num,ans,mod_x,have_x;
    if (pos <= 0)
        return mod==0&&have==2;
    if (!lim && dp[pos][mod][have]!=-1) //沒有上限且被訪問過
        return dp[pos][mod][have];
    ans = 0;
    num = lim?s[pos]:9;//如果有上限,只能取到當前位數,如果沒上限,可取到9
                        //假設該位是2,下一位是3,如果現在算到該位為1,那麼下一位是能取到9的,如果該位為2,下一位只能取到3
    for (int i=0; i<=num; i++)
    {
        mod_x = (mod*10+i)%13;//該位的每種情況對13取模
        have_x = have;
        if (have==0 && i==1)//末尾加1
            have_x=1;
        if (have==1 && i!=1)//末尾已經為1了
            have_x=0;
        if (have==1 && i==3)//末尾是1,現在加3
            have_x=2;
        ans+=dfs(pos-1, mod_x, have_x, lim&&i==num);//如果i==num,下一位能取的最大數就為s[pos-1],i!=num,下一位能取到9
    }
    if (!lim)
        dp[pos][mod][have] = ans;
    return ans;
}

int main ()
{
    int n,t;
    while (scanf (%d,&n)==1)
    {
        CL(s);
        memset(dp, -1, sizeof(dp));
        t = 0;
        while (n)
        {
            s[++t]=n%10;
            n/=10;
        }
        cout<

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved