利用數(shù)位DP的思想，從右相左依次判斷讓前i位完全活動(dòng)是否是可行方案，顯然第一個(gè)可行方案就是答案，將“自由活動(dòng)”的數(shù)位構(gòu)造一下就可以了。我沒有將digit1和digit2的大小排序，結(jié)果輸出了次優(yōu)解。
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 typedef
long long ll;
5 int hash[11];
6 bool fit(
long long N,
int a,
int &c1,
int b,
int &c2){
7 //cout<<N<<" ";
8 while(N){
9 ll x = N % 10;
10 if(x == a && c1) c1--;
11 if(x == b && c2) c2--;
12 N /= 10;
13 }
14 return !c1 && !c2;
15 }
16 ll cal(
int a,
int c1,
int b,
int c2){
17 cout<<"cal: "<<a<<" "<<c1<<" "<<b<<" "<<c2<<endl;
18 int n = c1+c2; ll ans = 0;
19 for(
int i=0; i < n; i++){
20 ans *= 10;
21 if(c1){
22 ans += a;
23 c1 --;
24 }
25 else {
26 ans += b;
27 c2 --;
28 }
29 }
30 return ans;
31 }
32 class FavouriteDigits{
33 public :
long long findNext(
long long N,
int digit1,
int count1,
int digit2,
int count2){
34 if(digit1 > digit2){ swap(digit1,digit2); swap(count1,count2); }
35 int cnt1 = count1, cnt2 = count2;
36 ll
base[20];
37 base[0] = 1;
38 for(
int i=1;i<20;i++)
base[i] =
base[i-1] * 10;
39 if(fit(N,digit1,cnt1,digit2,cnt2))
return N;
40 int flag = 0;
41 while(1){
42 ll D = N%10;
43 cnt1 = count1, cnt2 = count2;
44 ll M = N+1;
45 fit(M,digit1,cnt1,digit2,cnt2);
46 if(flag >= cnt1+cnt2)
return M*
base[flag] + cal(digit1,cnt1,digit2,cnt2);
47 cnt1 = count1, cnt2 = count2;
48 if(D < digit1){
49 M = N/10*10 + digit1;
50 fit(M,digit1,cnt1,digit2,cnt2);
51 if(flag >= cnt1+cnt2)
return M*
base[flag] + cal(digit1,cnt1,digit2,cnt2);
52 }
53 cnt1 = count1, cnt2 = count2;
54 if(D < digit2){
55 M = N/10*10 + digit2;
56 fit(M,digit1,cnt1,digit2,cnt2);
57 if(flag >= cnt1+cnt2)
return M*
base[flag] + cal(digit1,cnt1,digit2,cnt2);
58 }
59 N/=10; flag ++;
60 }
61 }
62 };