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.
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