2012-09-22 14:14:13Morris
[ZJ][建表非DP] a532. 奇特的數列
內容 ：
有一個數列的前十項：0、1、8、11、69、88、96、101、111、181，這個數列是在一次考古研究中發現，考古學家想要知道這個數列的後續發展，或許能預測人類的未來。你的任務是寫一支程式求得這個數列的任一項數值。
輸入說明
：
每行一個十進位正整數Ｎ（0＜Ｎ＜＝1000000），以Ｎ＝0代表輸入結束。
輸出說明
：
輸出一個非負整數，代表這個奇特數列的第Ｎ項
範例輸入 ：
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;
}
#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;
}