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

poj 3208 Apocalypse Someday(數位dp)

編輯:C++入門知識

poj 3208 Apocalypse Someday(數位dp)


題目鏈接:poj 3208 Apocalypse Someday

題目大意:給定n,輸出第n大包含666的數字。

解題思路:數位dp,用類似AC自動機的思想進行轉移。首先dp[i][j]表示說i位最後有j個連續6的情況數,這個預處理出

來。那麼dp[i][3]即為i位有多少個滿足的數。給定n,先確定位數d。然後從最高位向下判斷,一開始肯定是需要3個連續

的6,所以u為3,然後根據後面添加的數字動態修改u值進行判斷。

#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int maxd = 10;
const int status = 4;
const int g[4][12] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {3, 3, 3, 3, 3, 3, 0, 3, 3, 3},
    {3, 3, 3, 3, 3, 3, 1, 3, 3, 3},
    {3, 3, 3, 3, 3, 3, 2, 3, 3, 3}};

ll n, dp[maxd+5][status];

int main () {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= maxd; i++) {
        dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) * 9;
        dp[i][1] = dp[i-1][0];
        dp[i][2] = dp[i-1][1];
        dp[i][3] = dp[i-1][3] * 10 + dp[i-1][2];
    }

    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%lld", &n);

        int d = 0, u = 3;
        while (dp[d][3] < n)
            d++;

        while (d) {

            ll k = 0;

//            printf("%d:\n", d);
            for (int i = 0; i < 10; i++) {
                ll tmp = 0;

                for (int j = 3; j >= g[u][i]; j--)
                    tmp += dp[d-1][j];

//                printf("n:%lld status: %d %d %lld\n", n, u, i, tmp);
                if (k + tmp >= n) {
                    printf("%d", i);
                    u = g[u][i];
                    break;
                }
                k += tmp;
            }
            n -= k;
            d--;
        }
        printf("\n");
    }
    return 0;
}

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