Editorial for Trò chơi nhặt quà
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 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.
Comments