24h購物| | PChome| 登入
2012-09-22 14:14:13| 人氣1,097| 回應0 | 上一篇 | 下一篇

[ZJ][建表非DP] a532. 奇特的數列

推薦 0 收藏 0 轉貼0 訂閱站台

內容 :

有一個數列的前十項:0、1、8、11、69、88、96、101、111、181,這個數列是在一次考古研究中發現,考古學家想要知道這個數列的後續發展,或許能預測人類的未來。你的任務是寫一支程式求得這個數列的任一項數值。

輸入說明 :

每行一個十進位正整數N(0<N<=1000000),以N=0代表輸入結束。

輸出說明 :

輸出一個非負整數,代表這個奇特數列的第N項

範例輸入 :

1
2
3

範例輸出 :

0
1
8

提示 :

背景知識: DP

測資自己出的,有錯請提出><

出處 :

成功高中校內賽第五題 (管理:eddy841021)



#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
char s[20], buf[5] = {0,1,6,8,9};
int n = 0;
LL stk[2000000];
void dfs(int idx, LL head, LL tail, LL t) {
    if(head > 680000000)
        return;
    int i, tmp;
    if(idx > 0) {
        stk[n++] = head*t+tail;
        if(s[idx-1] != 6 && s[idx-1] != 9)
            stk[n++] = head*t/10+tail-s[idx-1]*t/10;
    }
    if(idx == 9)    return;
    for(i = 1-(idx!=0); i < 5; i++) {
        s[idx] = buf[i];
        tmp = s[idx];
        if(tmp == 6)        tmp = 9;
        else if(tmp == 9)   tmp = 6;
        dfs(idx+1, head*10+s[idx], tail+t*tmp, t*10);
    }
}
int main() {
    dfs(0,0,0,1);
    stk[n++] = 0;
    sort(stk, stk+n);
    while(scanf("%d", &n) == 1 && n)
        printf("%lld\n", stk[n-1]);
    return 0;
}

台長: Morris
人氣(1,097) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ] a528. 大數排序
此分類上一篇:[ZJ][dfs搜索+剪枝優化] d717. 好多因子

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文