Hướng dẫn giải của Chấm điểm
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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 max=200; var n,m,s:byte; a:array[1..20,1..20] of integer; b:array[0..20,1..20,0..max] of byte; d:array[1..20] of byte; procedure rf; var i,j:byte; begin readln(s,n,m); for i:=1 to m do begin for j:=1 to n do read(a[i,j]); readln; end; end; procedure pr; var i,j,k,p:integer; begin fillchar(b,sizeof(b),0); for i:=1 to m do b[1,i,a[i,1]]:=i; for i:=2 to n do for j:=1 to m do for k:=1 to s do for p:=1 to m do if (k>a[p,i]) and (b[i-1,j,k-a[p,i]]>0) and (a[j,i-1]<=a[p,i]) then b[i,p,k]:=j; end; procedure wf; var i,j,t:byte; kt:boolean; begin kt:=false; for i:=1 to m do if b[n,i,s]>0 then begin kt:=true; break; end; if kt then begin writeln('YES'); d[n]:=i; t:=s; for i:=n-1 downto 1 do begin d[i]:=b[i+1,d[i+1],t]; t:=t-a[d[i+1],i+1]; end; for i:=1 to n do write(a[d[i],i],' '); end else write('NO'); 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(); it != _e; ++it) #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 #define N 25 #define K 25 #define S 205 int s, k, n, f[K][S], a[K][N]; int main() { //freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); scanf( "%d%d%d", &s, &k, &n ); rep(j, n) rep(i, k) scanf( "%d", &a[i][j] ); rep(i, k+1) rep(j, s+1) { if( i == 0 && j == 0 ) f[i][j] = 0; else if ( i == 0 || j == 0 ) f[i][j] = INF; else { f[i][j] = INF; rep(x, n) if( a[i-1][x] < f[i][j] && a[i-1][x] <= j && f[i-1][j-a[i-1][x]] <= a[i-1][x] ) f[i][j] = a[i-1][x]; } } if( f[k][s] == INF ) puts("NO"); else { puts("YES"); stack<int> st; while( s != 0 ) { st.push(f[k][s]); s -= f[k--][s]; } for(;!st.empty(); st.pop()) printf( "%d ", st.top() ); putchar(10); } return 0; }
Code mẫu của ladpro98
program v8score;//dp uses math; const fi=''; var a,trace:array[0..21,0..21] of longint; f,check:array[0..21,0..21,0..200] of boolean; n,k,s:longint; procedure input; var inp:text; i,j:longint; begin assign(inp,fi); reset(inp); readln(inp,s,k,n); for i:=1 to n do begin for j:=1 to k do read(inp,a[i,j]); readln(inp); end; close(inp); end; procedure init; var i,j:longint; begin for i:=1 to n do begin f[i,0,0]:=true; check[i,0,0]:=true; a[i,0]:=low(longint); end; end; function dp(i,j,k:longint):boolean; var c:longint; begin if (k<a[i,j]) and (j<>0) then exit(false); if (check[i,j,k]) then exit(f[i,j,k]); check[i,j,k]:=true; for c:=1 to n do begin if a[c,j-1]>a[i,j] then continue; if dp(c,j-1,k-a[i,j]) then begin f[i,j,k]:=true; trace[i,j]:=c; exit(true); end; end; f[i,j,k]:=false; exit(false); end; procedure process; var i,j:longint; begin for i:=1 to n do dp(i,k,s); end; procedure output; var res:array[0..21] of longint; ok:boolean; i,j,hang:longint; begin ok:=false; for i:=1 to n do begin if dp(i,k,s) then begin writeln('YES'); hang:=i; for j:=k downto 1 do begin res[j]:=a[hang,j]; hang:=trace[hang,j]; end; ok:=true; break; end; end; if ok then for i:=1 to k do write(res[i],' ') else write('NO'); end; begin input; init; //process; output; end.
Code mẫu của RR
{$R+,Q+} const FINP=''; FOUT=''; MAXN=20; MAXS=200; var s,k,n:longint; trace,d:array[1..MAXN,1..MAXS,1..MAXN] of longint; c:array[1..MAXN,1..MAXN] of longint; procedure inp; var f:text; i,j:longint; begin assign(f,FINP); reset(f); read(f,s,k,n); for i:=1 to n do for j:=1 to k do read(f,c[i,j]); close(f); end; procedure solve; var sum,last,pre,i:longint; begin for i:=1 to n do d[k,c[i,k],i]:=1; for i:=k-1 downto 1 do for sum:=1 to s do for last:=1 to n do for pre:=1 to n do if (sum>c[last,i]) and (d[i+1,sum-c[last,i],pre]=1) and (c[last,i]<=c[pre,i+1]) then begin d[i,sum,last]:=1; trace[i,sum,last]:=pre; end; end; procedure ans; var f:text; i,j,sum,u:longint; begin assign(f,FOUT); rewrite(f); sum:=s; i:=1; while (i<=n) and (d[1,sum,i]=0) do inc(i); if i=n+1 then writeln(f,'NO') else begin writeln(f,'YES'); for j:=1 to k do begin write(f,c[i,j],' '); u:=sum-c[i,j]; i:=trace[j,sum,i]; sum:=u; end; end; close(f); end; begin inp; solve; ans; end.
Code mẫu của ll931110
Program V8SCORE; Const input = ''; output = ''; Var a: array[1..20,1..20] of integer; F: array[1..400,1..20] of integer; x: array[1..20] of integer; n,k,sum: integer; Procedure init; Var fi: text; i,j: integer; Begin Assign(fi, input); Reset(fi); Readln(fi, sum, k, n); For i:= 1 to n do Begin For j:= 1 to k do read(fi, a[i,j]); Readln(fi); End; Close(fi); End; Procedure optimize; Var i,s,t: integer; Begin Fillchar(F, sizeof(F), 0); For i:= 1 to n do F[a[i,1],1]:= a[i,1]; For t:= 1 to k - 1 do For i:= 1 to 200 do For s:= 1 to n do if (F[i,t] <> 0) and ((F[i + a[s,t + 1],t + 1] = 0) or (a[s,t + 1] < F[i + a[s,t + 1],t + 1])) and (a[s,t + 1] >= F[i,t]) then F[i + a[s,t + 1],t + 1]:= a[s,t + 1]; End; Procedure solve; Var fo: text; i: integer; Begin Assign(fo, output); Rewrite(fo); If F[sum,k] = 0 then writeln(fo, 'NO') else Begin For i:= k downto 1 do Begin x[i]:= F[sum,i]; sum:= sum - x[i]; End; Writeln(fo, 'YES'); For i:= 1 to k do write(fo, x[i], ' '); End; Close(fo); End; Begin init; optimize; solve; End.
Code mẫu của skyvn97
#include<stdio.h> int s,n,k; bool fin; int a[22][22]; int x[22]; int tmp; void swap(int &a,int &b) { int sw; sw=a;a=b;b=sw; } void init(void) { int i,j,l; scanf("%d",&s); scanf("%d",&k); scanf("%d",&n); for (i=1;i<=n;i=i+1) for (j=1;j<=k;j=j+1) scanf("%d",&a[i][j]); fin=false; for (i=1;i<=k;i=i+1) for (j=1;j<n;j=j+1) for (l=j+1;l<=n;l=l+1) if (a[j][i]<a[l][i]) swap(a[j][i],a[l][i]); tmp=0; x[0]=-1; } void print(void) { if (s!=tmp) return; printf("YES\n"); int i; for (i=1;i<k;i=i+1) printf("%d ",x[i]); printf("%d",x[k]); fin=true; } void btrk(int t) { int i; for (i=1;i<=n;i=i+1) { if (a[i][t]<x[t-1]) break; x[t]=a[i][t]; tmp=tmp+a[i][t]; if (s-tmp>=x[t]*(k-t)) { if (t==k) print(); else if (!fin) btrk(t+1); } tmp=tmp-a[i][t]; } } int main(void) { init(); btrk(1); if (!fin) printf("NO"); }
Code mẫu của khuc_tuan
var s, k, n : integer; F : array[0..20,0..200,0..200] of boolean; a : array[1..20,1..20] of integer; procedure nhap; var i, j : integer; begin read( s, k, n); for i:=1 to n do for j:=1 to k do read(a[i,j]); end; procedure qhd; var bai, gk, dmax, tong : integer; begin F[0,0,0] := true; for bai:=1 to k do begin for gk:=1 to n do begin for dmax:=0 to a[gk,bai] do begin for tong:=0 to s-a[gk,bai] do if F[bai-1,dmax,tong] then F[bai,a[gk,bai],tong+a[gk,bai]] := true; end; end; end; end; procedure truy( sb, dm, tong : integer); var gk, ndm : integer; ok : boolean; begin if sb=0 then exit; for gk:=1 to n do if (a[gk,sb]=dm) and (tong>=a[gk,sb]) then begin ok := false; for ndm:=0 to dm do if f[sb-1,ndm,tong-a[gk,sb]] then begin ok := true; truy( sb-1, ndm, tong - a[gk,sb]); write( a[gk,sb],' '); break; end; if ok then break; end; end; var dm : integer; co : boolean; begin nhap; qhd; co := false; for dm:=0 to s do if F[k,dm,s] then begin writeln('YES'); truy( k, dm, s); co := true; break; end; if not co then writeln('NO'); end.
Bình luận