Editorial for Chấm điểm
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 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.
Comments