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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.