POJ 3208 Apocalypse Someday（数位DP）

哎，不开long long 见祖宗...（学会了int魔改long long：

#define int long long

signed main(){

}

这道题是数位DP+二分，二分原因：随着数的增大，个数也呈递增的形式，所以二分找满足条件的最小的数即为答案。

然后在记录时i为当前一位，p1为前一位，p2为前两位，tag为曾经是否满足'666'。最后二分一个答案即可。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define int long long
 5 using namespace std;
 6 int dp[20][20][20][2];
 7 int a[20];
 8 int DFS(int pos,int p1,int p2,int tag,int limit){
 9     if(!pos) return tag;
10     if(!limit&&dp[pos][p1][p2][tag]!=-1) return dp[pos][p1][p2][tag];
11     int up=limit?a[pos]:9;
12     int ans=0;
13     for(int i=0;i<=up;i++)
14         ans+=DFS(pos-1,i,p1,tag||(p1==6&&p2==6&&i==6),limit&&i==a[pos]);
15     if(!limit) dp[pos][p1][p2][tag]=ans;
16     return ans;
17 }
18 int solve(int x){
19     int len=0;
20     while(x) a[++len]=x%10,x/=10;
21     return DFS(len,0,0,0,1);
22 }
23 signed main(){
24     int T,x;
25     memset(dp,-1,sizeof(dp));
26     scanf("%lld",&T);
27     while(T--){
28         scanf("%lld",&x);
29         int l=0,r=1e10;
30         while(l<r){
31             int mid=(l+r)>>1;
32             if(solve(mid)>=x) r=mid;
33             else l=mid+1;
34         }
35         printf("%lld
",r);
36     }
37     return 0;
38 }

AC代码