Editorial for Đổi tiền
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; maxc=100000; var n,s,re:longint; a:array[1..100] of longint; d:array[1..100] of byte; f:array[0..1,0..maxc] of longint; procedure rf; var i,t:longint; begin assign(input,fi); reset(input); readln(n,s); fillchar(d,sizeof(d),0); for i:=1 to n do begin read(t); d[t]:=1; end; t:=0; for i:=1 to 100 do if d[i]>0 then begin inc(t); a[t]:=i; end; close(input); end; procedure knap; var i,j,k,cur:longint; begin for i:=0 to maxc do f[1,i]:=i; for i:=2 to n do begin cur:=i mod 2; f[cur]:=f[1-cur]; for j:=1 to maxc do if (j>=a[i]) and (f[cur,j]>f[cur,j-a[i]]+1) then f[cur,j]:=f[cur,j-a[i]]+1; end; end; procedure pr; var i,j:longint; begin knap; if s>maxc then begin re:=(s-maxc) div a[n]; if (s-maxc) mod a[n]<>0 then inc(re); s:=s-re*a[n]; end; re:=re+f[n mod 2,s]; end; procedure wf; begin assign(output,fo); rewrite(output); write(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 int n, a[105], f[22222], s; int main() { scanf("%d%d",&n,&s); rep(i,n) scanf("%d",a+i); sort(a,a+n); int add = 0; if(s >= 20000) { add = (s - 20000) / a[n-1]; s -= add * a[n-1]; } fo(i,1,s) { f[i] = INF; for(int j = 0; a[j] <= i && j < n; ++j) f[i] = min(f[i], f[i-a[j]]+1); } printf("%d\n", f[s] + add); return 0; }
Code mẫu của ladpro98
program dtdoi; uses math; const maxn=111; maxV=10000; oo=1234567890; fi=''; var a:array[1..maxn] of longint; f:array[0..maxn,0..maxV] of longint; n,s,maxA,res:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,n,s); for i:=1 to n do begin read(inp,a[i]); maxA:=max(maxA,a[i]); end; close(inp); end; procedure process; var i,j,t:longint; begin //greedy if s>maxV then begin t:=(s-maxV) div maxA; s:=s-maxA*(t+1); res:=t+1; end; //dp f[0,0]:=0; for j:=1 to s do f[0,j]:=oo; for i:=1 to n do for j:=1 to s do begin f[i,j]:=f[i-1,j]; if j>=a[i] then f[i,j]:=min(f[i,j],f[i,j-a[i]]+1); end; end; begin input; process; write(res+f[n,s]); end.
Code mẫu của RR
//Written by RR {$R+,Q+} {$Mode objfpc} {$inline on} uses math; const FINP = ''; FOUT = ''; MAXN = 20111; var f1,f2 : text; n,s : longint; a : array[1..111] of longint; f : array[0..MAXN] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n,s); for i:=1 to n do read(f1,a[i]); end; procedure solve; var i,k:longint; begin fillchar(f,sizeof(f),$77); f[0]:=0; for i:=1 to MAXN do for k:=1 to n do if a[k]<=i then f[i]:=min(f[i],f[i-a[k]]+1); if s<=MAXN then writeln(f2,f[s]) else begin k:=0; for i:=1 to n do k:=max(k,a[i]); i:=MAXN; while i mod k<>0 do dec(i); i:=i-k+s mod k; writeln(f2,f[i]+(s-i) div k); end; end; begin openF; inp; solve; closeF; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int main() { int n,a[101],S,max = 0,f[10001]; scanf("%d %d",&n,&S); for(int i = 1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]>max) max = a[i]; } int KQ = 0; if(S>10000) { int d = (S-10000)/max+1; S = S - max*d; KQ = KQ+d; } f[0] = 0; for(int i = 1;i<=S;i++) { f[i] = 10000;max = 0; for(int j = 1;j<=n;j++) { if(i>=a[j] && f[i]>f[i-a[j]]+1) f[i] = f[i-a[j]]+1; } } KQ = KQ + f[S]; printf("%d",KQ); // getch(); }
Code mẫu của ll931110
#include <iostream> #define MAXN 101 #define MAXV 10000 #define MAXK 1000000000 using namespace std; int F[MAXV],a[MAXN],n,s; int main() { int i,j,k,max,res; //freopen("dtdoi.inp","r",stdin); //freopen("dtdoi.out","w",stdout); scanf("%d%d", &n, &s); max = 0; for (i = 1; i <= n; i++) { scanf("%d", &a[i]); if (max < a[i] && a[i] <= s) max = a[i]; } for (i = 0; i < MAXV; i++) F[i] = MAXK; F[0] = 0; for (i = 1; i < MAXV; i++) for (j = 1; j <= n; j++) if (i >= a[j]) if (F[i] > F[i - a[j]] + 1) F[i] = F[i - a[j]] + 1; if (s >= MAXV) { k = ((s - MAXV) / max) + 1; s -= k * max; } else k = 0; res = MAXK; do { if (res > k + F[s]) res = k + F[s]; k++; s -= max; } while (s >= 0); printf("%d", res); }
Code mẫu của skyvn97
#include<cstdio> #include<algorithm> #define MAX 111 using namespace std; const int mdp=60000; int n,s,mv; int v[MAX]; int f[MAX][mdp]; void init(void) { scanf("%d",&n); scanf("%d",&s); int i; mv=-1; for (i=1;i<=n;i=i+1) { scanf("%d",&v[i]); if (v[i]>mv) mv=v[i]; } sort(&v[1],&v[n+1]); } int min(const int &x,const int &y) { if (x<y) return (x); else return (y); } void optimize(void) { int i,j; for (i=1;i<=n;i=i+1) f[i][0]=0; for (i=1;i<mdp;i=i+1) f[1][i]=i; for (i=2;i<=n;i=i+1) for (j=1;j<mdp;j=j+1) { if (j<v[i]) f[i][j]=f[i-1][j]; else f[i][j]=min(f[i-1][j],f[i][j-v[i]]+1); } } void answer(void) { if (s<mdp) { printf("%d",f[n][s]); return; } int i; int best=(int)1e9; for (i=s/mv;i>=0;i=i-1) { if (s-mv*i>=mdp) break; best=min(best,i+f[n][s-mv*i]); } printf("%d",best); } int main(void) { init(); optimize(); answer(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; #define MAX 100000 int n, s; int a[111]; int F[MAX + 10]; int main() { scanf("%d%d", &n, &s); for(int i=0;i<n;++i) scanf("%d", a + i); memset( F, 0x1f, sizeof(F)); F[0] = 0; for(int i=0;i<MAX;++i) { for(int j=0;j<n;++j) if(i + a[j] <= MAX) F[i + a[j]] <?= F[i] + 1; } if(s <= MAX) cout << F[s] << endl; else { int best = 1000000000; for(int i=0;i<MAX;++i) for(int j=0;j<n;++j) if((s - i) % a[j] == 0) best <?= F[i] + (s - i) / a[j]; cout << best << endl; } // system("pause"); return 0; }
Comments