Hướng dẫn giải của VM 08 Bài 10 - Bộ lạc


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 maxn=51;
var a:array[0..maxn] of string;
    b,d,e,re:array[1..maxn] of longint;
    f:array[0..maxn,0..maxn,-1..maxn] of longint;
    n,x,y,z:longint;
    kq:ansistring;

procedure rf;
var i,t:longint;  c:char; code:integer; s:string;
begin
     readln(n);
     readln(x,y,z);
     for i:=1 to n do
     begin
          readln(a[i]);
          t:=pos(' ',a[i]);
          s:=copy(a[i],t+1,length(a[i])-t);
          delete(a[i],t,length(a[i])-t+1);
          val(s,b[i],code);
     end;
end;

procedure sort;
var i,j,t:longint; p:string;
begin
     for i:=1 to n-1 do
         for j:=i+1 to n do
             if a[i]<a[j] then
             begin
                  p:=a[i]; a[i]:=a[j]; a[j]:=p;
                  t:=b[i]; b[i]:=b[j]; b[j]:=t;
             end;
end;

procedure calc;
var i,j:longint;
begin
     for i:=1 to n do
         for j:=1 to length(a[i]) do
             if a[i,j]='a' then inc(d[i])
             else inc(e[i]);
end;

procedure pr;
var i,j,k,p:longint;
begin
     sort;
     calc;
     f[0,0,-1]:=1;
     for i:=1 to n do
       for j:=d[i] to x do
         for k:=e[i] to y do
           for p:=0 to z do
             if (f[j-d[i],k-e[i],p-1]>0) and (f[j,k,p]<f[j-d[i],k-e[i],p-1]+b[i]) then
                f[j,k,p]:=f[j-d[i],k-e[i],p-1]+b[i];
end;

procedure att(j,k,p:longint);
var i,last:longint; s:ansistring;
begin
     fillchar(re,sizeof(re),0);
     last:=n;
     while p>=0 do
     begin
          for i:=last downto 1 do
              if (d[i]<=j) and (e[i]<=k) and (f[j,k,p]=f[j-d[i],k-e[i],p-1]+b[i]) then
              begin
                   inc(re[i]);
                   j:=j-d[i]; k:=k-e[i]; p:=p-1;
                   last:=i;
                   break;
              end;
     end;
     for i:=n downto 1 do
         for j:=1 to re[i] do
             s:=s+a[i]+' ';
     if s<kq then kq:=s;
end;

procedure trace;
var i,jj,kk,pp,j,k,p,last,res:longint;
begin
     kq:='z';
     res:=0;
     for j:=0 to x do
         for k:=0 to y do
             for p:=-1 to z do
                 if f[j,k,p]>res then
                    res:=f[j,k,p];
     for j:=0 to x do
         for k:=0 to y do
             for p:=-1 to z do
                 if f[j,k,p]=res then att(j,k,p);
     writeln(kq);
end;

begin
     rf;
     pr;
     trace;
end.

Code mẫu của ladpro98

{$H+}
program TRIBE;
uses    math,sysutils;
const   maxn=50;
        fi='';
type    e=record
                a,b,w:longint;
                s:string;
        end;
var     f,choose:array[0..maxn,0..maxn,0..maxn] of longint;
        n,mx,my,mz,d:longint;
        p:array[1..maxn] of e;

procedure input;
var     inp:text;
        i,j:longint;
        s:string;
        te:e;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        readln(inp,mx,my,mz);
        for i:=1 to n do begin
                readln(inp,s);
                for j:=1 to length(s) do begin
                        if s[j] = ' ' then break;
                        if s[j] = 'a' then inc(p[i].a)
                        else inc(p[i].b);
                end;
                p[i].w:=StrToInt(copy(s,j+1,length(s)-j));
                p[i].s:=copy(s,1,j-1);
        end;
        close(inp);
        for i:=1 to n do
        for j:=i+1 to n do
        if p[i].s>p[j].s then begin
                te:=p[i];
                p[i]:=p[j];
                p[j]:=te;
        end;
end;

procedure dp;
var     i,x,y,z:longint;
begin
        for x:=0 to mx do
        for y:=0 to my do
        for z:=1 to mz+1 do
        begin
                for i:=1 to n do
                if (x>=p[i].a) and (y>=p[i].b) and (f[x,y,z]<f[x-p[i].a,y-p[i].b,z-1]+p[i].w) then begin
                        f[x,y,z]:=f[x-p[i].a,y-p[i].b,z-1]+p[i].w;
                        choose[x,y,z]:=i;
                end;
        end;
end;

procedure output;
var     i,x,y,z:longint;
begin
        x:=mx;y:=my;z:=mz+1;
        while choose[x,y,z]>0 do
        begin
                d:=choose[x,y,z];
                dec(x,p[d].a);
                dec(y,p[d].b);
                dec(z);
                write(p[d].s);
                if choose[x,y,z]>0 then write(' ');
        end;
end;

begin
        input;
        dp;
        output;
end.

Code mẫu của RR

{$R+,Q+}
program TRIBE;
const
  FINP='';
  FOUT='';
  MAXN=52;
type
  st=string[MAXN];
var
  a,b,c,n:longint;
  cost,sa,sb:array[1..MAXN] of longint;
  word:array[1..MAXN] of st;
  pre,d:array[0..MAXN,0..MAXN,0..MAXN] of longint;
procedure inp;
var
  ch:char;
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  readln(f,a,b,c);
  for i:=1 to n do
    begin
      repeat
        read(f,ch);
        if ch<>' 'then word[i]:=word[i]+ch;
        if ch='a' then inc(sa[i])
        else if ch='b' then inc(sb[i]);
      until ch=' ';
      readln(f,cost[i]);
    end;
  close(f);
end;
procedure init;
var
  i:longint;
begin
  for i:=1 to MAXN do
    begin
      word[i]:='';
      sa[i]:=0; sb[i]:=0;
      cost[i]:=0;
    end;
end;
procedure solve;
var
  i,aa,bb,u:longint;
begin
  for i:=1 to c+1 do
  begin
    for u:=1 to n do
    for aa:=0 to a do
    for bb:=0 to b do
      if (aa>=sa[u]) and (bb>=sb[u]) then
        if d[i,aa,bb]<d[i-1,aa-sa[u],bb-sb[u]]+cost[u] then
          begin
            d[i,aa,bb]:=d[i-1,aa-sa[u],bb-sb[u]]+cost[u];
            pre[i,aa,bb]:=u;
          end;
  end;
end;
procedure ans;
var
  f:text;
  i,aa,bb,li,la,lb:longint;
  procedure trace(i,a,b:longint);
  var
    u:longint;
  begin
    u:=pre[i,a,b];
    if u=0 then exit;
    write(f,word[u]);
    if i<li+1 then write(f,' ');
    if i>1 then trace(i-1,a-sa[u],b-sb[u]);
  end;
begin
  assign(f,FOUT); rewrite(f);
  li:=0; la:=0; lb:=0;
  for i:=c+1 downto 1 do
  for aa:=0 to a do
  for bb:=0 to b do
    if d[i,aa,bb]>d[li,la,lb] then
      begin
        li:=i;
        la:=aa;
        lb:=bb;
      end;
  if li>0 then trace(li,la,lb);
  close(f);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure swaps(var a,b:st);
var
  temp:st;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
  i,j:longint;
  mid:st;
begin
  mid:=word[(l+r) div 2];
  i:=l; j:=r;
  repeat
    while word[i]<mid do inc(i);
    while word[j]>mid do dec(j);
    if i<=j then
      begin
        swaps(word[i],word[j]);
        swap(sa[i],sa[j]);
        swap(sb[i],sb[j]);
        swap(cost[i],cost[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
begin
  init;
  inp;
  sort(1,n);
  solve;
  ans;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n,x,y,z,gt[51],soa[51],sob[51],f[51][51][55],temp;
string s[51],the1,the2,the; 

int main(){
     //freopen("TRIBE.in","r",stdin);
     scanf("%d %d %d %d",&n,&x,&y,&z);
     for(int i = 1;i<=n;i++)
          cin>>s[i]>>gt[i];
     memset(f,0,sizeof(f)); 
     for(int i = 1;i<=n;i++)
          for(int j = 1;j<=n;j++){
                the1 = s[i]+' '+s[j];
                the2 = s[j]+' '+s[i];
                if(the1.compare(the2)<0){
                     the = s[i];
                     s[i] = s[j];
                     s[j] = the;
                     temp = gt[i];
                     gt[i] = gt[j];
                     gt[j] = temp;
                }  
          }
     for(int i = 1;i<=n;i++){
          soa[i] = 0; sob[i] = 0;
          for(int j = 0;j<s[i].length();j++)
                if(s[i][j]=='a') soa[i]++;
                else sob[i]++;
     }

     for(int i = 1;i<=z+1;i++){
           for(int tx = 0;tx<=x;tx++)
                 for(int ty=0;ty<=y;ty++){
                      f[tx][ty][i] = f[tx][ty][i-1];
                      for(int j = 1;j<=n;j++)
                           if(tx-soa[j]>=0 && ty-sob[j]>=0)
                                 f[tx][ty][i] >?= f[tx-soa[j]][ty-sob[j]][i-1]+ gt[j];
                 }
     }
     z++;
     int run = f[x][y][z];
     //printf("%d\n",run);
     //while(f[x][y][z] == f[x][y][z-1]) z--;
     int l;
     while(z>0){
           l = z;     
          // printf("%d %d %d %d\n",run,x,y,z);     
           for(int i = 1;i<=n;i++){
                if(x>=soa[i] && y>=sob[i])
                     if(run == f[x-soa[i]][y-sob[i]][z-1]+gt[i]){
                            cout<<s[i]<<" ";
                            run -= gt[i];
                            x -= soa[i];
                            y -= sob[i];
                            z--;
                            break;
                     }
           }
           if(l==z) z--;
          // printf("%d %d %d %d\n",run,x,y,z);
           //getch();
     }
    // getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int f[52][52][52];
vector< pair<string,int> > v;
string s[52];
int a[52],b[52],val[52];
int n,maxx,maxy,maxz;

int rec(int x,int y,int z)
{
     if (f[x][y][z] != -1) return f[x][y][z];
     int best = 0;
     if (!z) 
     {
        for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i]) best = max(best,val[i]);
     }
     else
       for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i]) best = max(best,rec(x - a[i],y - b[i],z - 1) + val[i]);
     f[x][y][z] = best;  return best;
};

void track(int x,int y,int z,bool first)
{
     if (!f[x][y][z]) return;
     if (!first) printf(" ");
     if (!z)
     {
       for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i] && f[x][y][z] == val[i])
       {
           cout << s[i]; break;
       };
     }
     else
     for (int i = 0; i < n; i++) 
       if (x >= a[i] && y >= b[i] && f[x][y][z] == val[i] + rec(x - a[i],y - b[i],z - 1))
       {
             cout << s[i];  track(x - a[i],y - b[i],z - 1,false);  break;       
       };
};

int main()
{
//    freopen("tribe.in","r",stdin);
//    freopen("tribe.ou","w",stdout);
    scanf("%d", &n);
    scanf("%d %d %d", &maxx, &maxy, &maxz);
    for (int i = 0; i < n; i++)
    {
        string st;  int k;
        cin >> st >> k;
        v.push_back(make_pair(st,k));        
    };
    sort(v.begin(),v.end());
    for (int i = 0; i < n; i++)
    {
        a[i] = 0;  b[i] = 0; s[i] = v[i].first; val[i] = v[i].second;
        for (int j = 0; j < s[i].size(); j++) if (s[i][j] == 'a') a[i]++; else b[i]++;
    };
    memset(f,-1,sizeof(f));
    int tmp = rec(maxx,maxy,maxz);
    track(maxx,maxy,maxz,true);  
};

Code mẫu của khuc_tuan

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    static class Word {
        String w;
        int na, nb;
        int value;
    }

    static int n;
    static int x, y, z;
    static Word[] a;
    static int[][][][] F;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        x = sc.nextInt();
        y = sc.nextInt();
        z = sc.nextInt();
        sc.nextLine();
        a = new Word[n];
        for (int i = 0; i < n; ++i) {
            String[] tmp = sc.nextLine().split(" ");
            a[i] = new Word();
            a[i].w = tmp[0];
            a[i].value = Integer.parseInt(tmp[1]);
        }
        Arrays.sort(a, new Comparator<Word>() {
            public int compare(Word w1, Word w2) {
                return w1.w.compareTo(w2.w);
            }
        });
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < a[i].w.length(); ++j)
                if (a[i].w.charAt(j) == 'a')
                    ++a[i].na;
                else
                    ++a[i].nb;
        F = new int[x + 1][y + 1][z + 1][2];
        for (int[][][] a3 : F)
            for (int[][] a2 : a3)
                for (int[] a1 : a2)
                    Arrays.fill(a1, -1);
        System.out.println(truyvet(x, y, z, 0));
    }

    static String truyvet(int x, int y, int z, int need) {
        int res = calc(x, y, z, need);
        // if (z > 0 && res == calc(x, y, z - 1, 0))
        // return " " + truyvet(x, y, z - 1, 0);
        for (int k = 0; k < a.length; ++k) {
            if (a[k].na <= x && a[k].nb <= y && z - need >= 0) {
                int now = calc(x - a[k].na, y - a[k].nb, z - need, 1);
                if (res == now + a[k].value)
                    return (need == 0 ? "" : " ") + a[k].w
                            + truyvet(x - a[k].na, y - a[k].nb, z - need, 1);
            }
        }
        return "";
    }

    static int calc(int x, int y, int z, int need) {
        if (F[x][y][z][need] != -1)
            return F[x][y][z][need];

        int res = 0;
        // if (z > 0)
        // res = Math.max(res, calc(x, y, z - 1, 0));

        for (int k = 0; k < a.length; ++k)
            if (a[k].na <= x && a[k].nb <= y && z - need >= 0) {
                int now = calc(x - a[k].na, y - a[k].nb, z - need, 1);
                res = Math.max(res, now + a[k].value);
            }

        return F[x][y][z][need] = res;
    }
}

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.