Hướng dẫn giải của Trò chơi nhặt quà
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 ladpro98
program SCOLLECT; uses math; const fi = ''; maxn = 135; oo = trunc(1e9); dx : array[1..2] of longint = (-1,0); dy : array[1..2] of longint = (0,-1); var a:array[0..maxn,0..maxn] of longint; f:array[0..maxn,0..maxn,0..maxn] of longint; chk:array[0..maxn,0..maxn,0..maxn] of boolean; inp:text; c:char; m,n,i,j,res:longint; Function DP(i,j,x,y:longint):longint; var d1,d2,xx,yy,ii,jj,plus:longint; begin if chk[i,j,x] then exit(f[i,j,x]); chk[i,j,x] := true; if (i = 1) and (j = 1) then begin f[i,j,x] := a[1,1]; exit(a[1,1]); end; if (i<1) or (j<1) or (x<1) or (y<1) or (i>m) or (j>n) or (x>m) or (y>n) or (a[i,j] = -1) or (a[x,y] = -1) then begin f[i,j,x] := -oo; exit(-oo); end; if (i = x) and (j = y) then plus := a[i,j] else plus := a[i,j] + a[x,y]; f[i,j,x] := -oo; for d1:=1 to 2 do for d2:=1 to 2 do begin ii := i + dx[d1]; jj := j + dy[d1]; xx := x + dx[d2]; yy := y + dy[d2]; f[i,j,x] := max(f[i,j,x], DP(ii, jj, xx, yy) + plus); end; exit(f[i,j,x]); end; procedure Input; begin assign(inp,fi);reset(inp); readln(inp,n,m); for i:=1 to m do begin for j:=1 to n do begin read(inp,c); if c = '*' then a[i,j]:=1; if c = '#' then a[i,j]:=-1; end; readln(inp); end; end; begin Input; res := max(0,DP(m,n,m,n)); write(res); end.
Code mẫu của RR
{$R+,Q+} {$Mode objFPC} uses math; const FINP=''; FOUT=''; MAXN=130; var f1,f2:text; test,m,n:longint; a:array[0..MAXN,0..MAXN] of longint; d:array[0..MAXN,0..MAXN,0..MAXN] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var ch:char; i,j:longint; begin readln(f1,n,m); for i:=1 to m do begin for j:=1 to n do begin read(f1,ch); case ch of '*': a[i,j]:=1; '.': a[i,j]:=0; '#': a[i,j]:=-1000000; end; end; readln(f1); end; end; procedure solve; var row,i,j:longint; begin for i:=1 to n do d[1,1,i]:=d[1,1,i-1]+a[1,i]; for i:=2 to n do for j:=i to n do d[1,i,j]:=d[1,i-1,j]; for row:=2 to m do begin for i:=1 to n do d[row,i,i]:=d[row-1,i,i]+a[row,i]; for i:=1 to n do for j:=i+1 to n do d[row,i,j]:=d[row-1,i,j]+a[row,i]+a[row,j]; for i:=1 to n do for j:=i+2 to n do d[row,i+1,j]:=max(d[row,i+1,j],d[row,i,j]+a[row,i+1]); for i:=2 to n do d[row,i,i]:=max(d[row,i,i],d[row,i-1,i]); for i:=2 to n do d[row,i,i]:=max(d[row,i,i],d[row,i-1,i-1]+a[row,i]); for i:=1 to n do for j:=i to n-1 do d[row,i,j+1]:=max(d[row,i,j+1],d[row,i,j]+a[row,j+1]); end; end; procedure ans; begin if d[m,n,n]<0 then d[m,n,n]:=0; writeln(f2,d[m,n,n]); end; begin openF; // readln(f1,test); test:=1; for test:=1 to test do begin inp; solve; ans; end; closeF; end.
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <ctime> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <iostream> #include <map> #include <set> #include <sstream> #include <stack> #include <queue> #include <vector> #include <utility> using namespace std; int f[260][130][130]; char a[130][130]; bool reach[130][130]; int m,n; int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; void DFS(int x,int y) { for (int i = 0; i < 4; i++) { int px = x + dx[i],py = y + dy[i]; if (px < 0 || px >= m || py < 0 || py >= n || reach[px][py] || a[px][py] == '#') continue; reach[px][py] = true; DFS(px,py); } } int rec(int step,int x,int y) { if (f[step][x][y] > -1) return f[step][x][y]; if (step == m + n - 1) return f[step][x][y] = 0; int best = 0; for (int px = 0; px < 2; px++) for (int py = 0; py < 2; py++) { int tx = x + px,ty = y + py; int sx = step + 1 - tx,sy = step + 1 - ty; if (tx > ty || ty >= n || sx >= m || a[sx][tx] == '#' || a[sy][ty] == '#') continue; int tmp = rec(step + 1,tx,ty); if (a[sx][tx] == '*') tmp++; if (ty > tx && a[sy][ty] == '*') tmp++; best = max(best,tmp); } return f[step][x][y] = best; } int main() { // freopen("tour.in","r",stdin); // freopen("tour.ou","w",stdout); scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) while (1) { scanf("%c", &a[i][j]); if (a[i][j] == '.' || a[i][j] == '*' || a[i][j] == '#') break; } memset(f,-1,sizeof(f)); memset(reach,false,sizeof(reach)); if (a[0][0] != '#') { reach[0][0] = true; DFS(0,0); } if (!reach[m - 1][n - 1]) printf("0\n"); else printf("%d\n", ((a[0][0] == '*') ? 1 : 0) + rec(0,0,0)); }
Code mẫu của khuc_tuan
//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1} // {$APPTYPE CONSOLE} {$mode delphi} uses Math; type Edge = class; List = class e : Edge; n : List; end; Node = class trace : Edge; id, fx : integer; ke : List; ken : List; constructor init(id, fx : integer); end; Edge = class u, v : Node; flow, cost, cap: integer; constructor init(u, v : Node; cost, cap : integer); end; procedure AddList(var l : List; e : Edge); var p : List; begin p := List.Create; p.e := e; p.n := l; l := p; end; constructor Node.init(id, fx : integer); begin self.id := id; self.fx := fx; end; constructor Edge.init(u, v : Node; cost, cap : integer); begin self.u := u; self.v := v; self.cost := cost; self.cap := cap; self.flow := 0; AddList(u.ke, self); AddList(v.ken, self); end; var kk, i, j, nlist, nodecount, m, n : integer; a : array[1..150,0..300] of char; source, dest : array[1..150,1..150] of Node; start, finish : Node; // vs : array[1..50000] of boolean; EdgeList : array[1..100000] of Edge; res : integer; dist : array[0..50000] of integer; { function calccost(e : Edge) : integer; begin calccost := e.u.fx + e.cost - e.v.fx; end; function dfs(u : Node) : boolean; var p : List; begin if u.id = finish.id then begin dfs := true; exit; end; if vs[u.id] then begin dfs := false; exit; end; vs[u.id] := true; p := u.ke; while p<>nil do begin if (calccost(p.e)=0) and (p.e.flow < p.e.cap) then begin if dfs(p.e.v) then begin inc(p.e.flow); res := res + p.e.cost; dfs := true; exit; end; end; p := p.n; end; p := u.ken; while p<>nil do begin if (calccost(p.e)=0) and (p.e.flow > 0) then begin if dfs(p.e.u) then begin dec(p.e.flow); res := res - p.e.cost; dfs := true; exit; end; end; p := p.n; end; dfs := false; end; procedure suanhan; var dmin, i, j : integer; e : Edge; begin dmin := 1000000000; for i:=1 to nlist do begin e := edgelist[i]; if vs[e.u.id] and (not vs[e.v.id]) and (e.flow < e.cap) then dmin := min(dmin,calccost(e)); if vs[e.v.id] and (not vs[e.u.id]) and (e.flow > 0) then dmin := min(dmin,-calccost(e)); end; for i:=1 to m do for j:=1 to n do begin if not vs[source[i,j].id] then inc(source[i,j].fx, dmin); if not vs[dest[i,j].id] then inc(dest[i,j].fx, dmin); end; end; } const MAXQ = 1000000; var Q : array[0..MAXQ] of Node; lq, rq : integer; procedure add(n : Node); begin inc(rq); if rq > MAXQ then rq := 1; Q[rq] := n; end; function pop : Node; begin pop := Q[lq]; if lq = rq then begin lq := 1; rq := 0; end else begin inc(lq); if lq > MAXQ then lq := 1; end; end; procedure findbest; var u, v : Node; p : List; begin lq := 1; rq := 0; add(start); fillchar( dist, sizeof(dist), $1f); dist[start.id] := 0; while rq <> 0 do begin u := pop; p := u.ke; while p<>nil do begin if (p.e.flow < p.e.cap) and (dist[p.e.v.id] > dist[u.id] + p.e.cost) then begin dist[p.e.v.id] := dist[u.id] + p.e.cost; p.e.v.trace := p.e; add(p.e.v); end; p := p.n; end; p := u.ken; while p<>nil do begin if (p.e.flow > 0) and (dist[p.e.u.id] > dist[u.id] - p.e.cost) then begin dist[p.e.u.id] := dist[u.id] - p.e.cost; p.e.u.trace := p.e; add(p.e.u); end; p := p.n; end; end; v := finish; if dist[v.id] = dist[0] then exit; while v<>start do begin if v=v.trace.v then begin inc(v.trace.flow); inc(res, v.trace.cost); v := v.trace.u; end else begin dec(v.trace.flow); dec(res,v.trace.cost); v := v.trace.v; end; end; end; begin readln(n, m); for i:=1 to m do begin readln(a[i]); move( a[i][0], a[i][1], 150); end; nlist := 0; nodecount := 0; for i:=1 to m do for j:=1 to n do begin inc(nodecount); source[i,j] := Node.init(nodecount,1000000 - nodecount); inc(nodecount); dest[i,j] := Node.init(nodecount,1000000 - nodecount); if a[i,j]='*' then begin inc(nlist); EdgeList[nlist] := Edge.init(source[i,j], dest[i,j], -1, 1); end; if (a[i,j]='*') or (a[i,j]='.') then begin inc(nlist); EdgeList[nlist] := Edge.init(source[i,j], dest[i,j], 0, 10); end; end; for i:=1 to m do for j:=1 to n do begin if i<m then begin inc(nlist); EdgeList[nlist] := Edge.init(dest[i,j], source[i+1,j], 0, 10); end; if j<n then begin inc(nlist); EdgeList[nlist] := Edge.init(dest[i,j], source[i,j+1], 0, 10); end; end; start := source[1,1]; finish := dest[m,n]; for kk:=1 to 2 do findbest(); { for kk:=1 to 2 do begin fillchar( vs, sizeof(vs), false); while(not dfs(start)) do begin suanhan; fillchar( vs, sizeof(vs), false); end; end; } writeln(-res); end.
Bình luận