Đề bài:
Thuật toán:
- Bài này sử dụng phương pháp đệ quy có nhớ
- (thuật toán đang cập nhập)
Bạn có thể đọc code để hiểu rõ hơn.
Code:
Pascal
const fi=''; fo=''; maxn=20; var a,b,tg1,tg2 : int64; aa : array[1..maxn] of longint; i,j,n,k,d : longint; f : array[0..maxn,0..maxn,0..maxn,false..true,false..true] of int64; procedure swap(var x,y : longint); var tg : longint; begin tg:=x;x:=y;y:=tg; end; procedure chuanbi(x : int64; var n : longint); var i,j : longint; begin n := 0; while x>0 do begin inc(n); aa[n] := x mod 10; x := x div 10; end; i:=1; j:=n; while (i<j) do begin swap(aa[i],aa[j]); inc(i);dec(j); end; end; function tinh(i,tr,sl : longint; big0, small :boolean) : int64; var j,tg : longint; dem : int64; begin if f[i,tr,sl,big0,small] > -1 then exit(f[i,tr,sl,big0,small]); if i>n then if (sl<=k) and (small) then exit(1) else exit(0); dem := 0; if not small then begin for j := 0 to aa[i] do begin if big0 then tg := sl + ord(abs(j-tr)<=d) else tg := 0; dem := dem + tinh(i+1,j,tg,big0 or (j>0),small or (j<aa[i])); end; end else begin for j := 0 to 9 do begin if big0 then tg := sl + ord(abs(j-tr)<=d) else tg := 0; dem := dem + tinh(i+1,j,tg,big0 or (j>0),small or (j<aa[i])); end; end; f[i,tr,sl,big0,small] := dem; exit(dem); end; begin assign(input,fi);reset(input); assigN(output,fo);rewrite(output); readln(a,b,d,k); chuanbi(a, n); fillchar(f,sizeof(f),255); tg1 := tinh(1,0,0,false,false); chuanbI(b+1, n); fillchar(f,sizeof(f),255); tg2 := tinh(1,0,0,false,false); writeln(tg2-tg1); close(input);close(output); end. |
C++
#include <bits/stdc++.h> #define FORE(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) #define FOR(i, a, b) for(int i = a; i < b; i++) const int MAXN = 1e5 * 5; const int INF = 1e9 + 7; using namespace std; long long l, r, D, K, n; long long f[20][10][20][2][2]; int a[20]; bool check(long long x) { bool ans = 1; int top = 0; int tmp = x; while (tmp){ a[++top] = tmp % 10; tmp /= 10; } reverse(a + 1, a + top + 1); int dem = 0; FORE(i, 2, top) if (abs(a[i] - a[i - 1]) <= D) dem++; //if (x == 103) cout << dem<<" "<<K<<"??"<<endl; return (dem <= K); } long long trau() { long long ans = 0; FORE(i, l, r) if (check(i)) ans++; cout << ans << endl; return 0; } long long duyet(int i, int dig, int worse, bool ok, bool greater0) { if (i > n){ return (worse <= K && greater0 > 0); } if (f[i][dig][worse][ok][greater0] > -1) return f[i][dig][worse][ok][greater0]; long long ans = 0; if (i == 1){ FORE(x, 0, a[i]) ans += duyet(i + 1, x, worse, ok | (x < a[i]), (x > 0)); } else { int last = 9; if (ok == 0) last = a[i]; int wnext; //if (i == 3) cout << last << "??"<<endl; FORE(x, 0, last) { if (greater0 == 0) wnext = worse; else wnext = worse + (abs(x - dig) <= D); //if (last == 3) cout << x<< ' '<<dig<<" "<<wnext<<endl; ans += duyet(i + 1, x, wnext, ok | (x < a[i]), greater0 | (x > 0)); } } f[i][dig][worse][ok][greater0] = ans; return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE freopen("DEMSO.inp", "r", stdin); freopen("DEMSO.out", "w", stdout); #endif //MIKELHPDATKE cin >> l >> r >> D >> K; //trau(); long long tmp = r, top = 0; while (tmp){ a[++top] = tmp % 10; tmp /= 10; } reverse(a + 1, a + top + 1); n = top; memset(f, -1, sizeof(f)); long long ans = duyet(1, 0, 0, 0, 0); // cout << ans << endl; tmp = l - 1, top = 0; while (tmp){ a[++top] = tmp % 10; tmp /= 10; } reverse(a + 1, a + top + 1); n = top; memset(f, -1, sizeof(f)); if (l - 1 == 0) cout << ans; else{ ans -= duyet(1, 0, 0, 0, 0); cout << ans; } //cout<<check(103)<<endl; return 0; } |
Speak Your Mind