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.

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

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.