BONUS13 – spoj

Đề bài:

Thuật toán:

Code:

uses    math;
const   fi='';
        fo='';
        maxn=80;
        n=8;
        hx:array[1..8] of integer=(-1,-2,-2,-1,1,2,2,1);
        hy:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2);
type    point=record
                x,y:byte;
                end;
var     cx,dx:array[1..maxn] of point;
        a:array[1..8,1..8] of boolean;
        c:array[1..maxn] of longint;
        i,j,k:longint;
        top1,top2:longint;
        hau,xe,ma,tuong:array[1..maxn,1..maxn] of boolean;
        m,t,x,h : longint;
        res:int64;
procedure nhap;
var     u,v:byte;
        w:longint;
begin
    assign(input,fi);reset(input);
    readln(k);
    for i:=1 to k do
        begin
            readln(u,v,w);
            a[u,v]:=true;
            inc(top1); dx[top1].x:=u; dx[top1].y:=v; c[top1]:=w;
        end;
    close(input);
end;
procedure init;
begin
    res:=0;
    for i:=1 to 8 do
        for j:=1 to 8 do
                if a[i,j]=false then
                        begin
                               inc(top2);
                               cx[top2].x:=i;
                               cx[top2].y:=j;
                        end;
end;
function chau(i,j:longint):boolean;
begin
    if cx[i].x=dx[j].x then exit(true);
    if cx[i].y=dx[j].y then exit(true);
    if (cx[i].x+cx[i].y)=(dx[j].x+dx[j].y) then exit(true);
    if (cx[i].x-cx[i].y)=(dx[j].x-dx[j].y) then exit(true);
    exit(false);
end;
function cxe(i,j:longint):boolean;
begin
    if cx[i].x=dx[j].x then exit(true);
    if cx[i].y=dx[j].y then exit(true);
    exit(false);
end;
function ctuong(i,j:longint):boolean;
begin
    if (cx[i].x+cx[i].y)=(dx[j].x+dx[j].y) then exit(true);
    if (cx[i].x-cx[i].y)=(dx[j].x-dx[j].y) then exit(true);
    exit(false);
end;
function cma(i,j:longint):boolean;
var     k,u,v:integer;
begin
    for k:=1 to 8 do
        begin
            u:=cx[i].x+hx[k];
            v:=cx[i].y+hy[k];
            if (u=dx[j].x) and (v=dx[j].y) then exit(true);
        end;
    exit(false);
end;
procedure xuly;
var     i,j:longint;
begin
    for i:=1 to top2 do
        for j:=1 to top1 do
         begin
          if chau(i,j) then hau[i,j]:=true;
          if cxe(i,j) then xe[i,j]:=true;
          if cma(i,j) then ma[i,j]:=true;
          if ctuong(i,j) then tuong[i,j]:=true;
         end;
end;
procedure main;
var     tam:int64;
begin
    for h:=1 to top2 do
        for x:=1 to top2 do
                if h<>x then
                        for m:=1 to top2 do
                                if (m<>h) and (m<>x) then
                                        for t:=1 to top2 do
                                                if (m<>t) and (t<>x) and (t<>h) then
                                                  begin
                                                        tam:=0;
                                                        for i:=1 to top1 do
                                                                if hau[h,i] or xe[x,i] or ma[m,i] or tuong[t,i] then tam := tam + c[i];
                                                        res:=max(res,tam);
                                                  end;
 
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    main;
    inkq;
end.
#include <iostream>
#include <vector>
using namespace std;
#define LL long long
#define rep(i, a, b) for (int i=a; i<b; i++)
 
struct pack {int x, y; LL w;};
 
inline LL calc(LL state, vector<pack>& a) {
    LL res = 0;
    for (auto &x: a) {
        if (state & 1) res += x.w;
        state >>= 1;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int m; cin >> m;
    vector<pack> a(m);
    vector<bool> frei(64, true);
    for (auto &a: a) {
        cin >> a.x >> a.y >> a.w;
        a.x--, a.y--;
        frei[a.x*8+a.y] = false;
    }
    vector<LL> xe(64, 0), tuong(64, 0), ma(64, 0), hau(64, 0);
    int c = 0;
    rep(i, 0, 8) rep(j, 0, 8) if (frei[c]) {
        rep(k, 0, m) {
            int x = a[k].x, y = a[k].y;
            if (x==i || y==j) xe[c] |= 1ll<<k;
            if (x-y==i-j || x+y==i+j) tuong[c] |= 1ll<<k;
            if ((abs(i-x)==2&&abs(j-y)==1) || (abs(i-x)==1&&abs(j-y)==2)) {
                ma[c] |= 1ll<<k;
            }
        }
        hau[c] = xe[c] | tuong[c];
        c++;
    } else c++;
 
    LL kq = 0;
    rep(h, 0, 64) if (frei[h]) {
        LL s = hau[h];
        frei[h] = false;
        rep(x, 0, 64) if (frei[x]) {
            LL bk = s;
            s |= xe[x];
            frei[x] = false;
            rep(t, 0, 64) if (frei[t]) {
                LL bk = s;
                frei[t] = false;
                s |= tuong[t];
                rep(m, 0, 64) if (frei[m]) {
                    kq = max(kq, calc(s | ma[m], a));
                }
                frei[t] = true;
                s = bk;
            }
            frei[x] = true;
            s = bk;
        }
        frei[h] = true;
    }
    cout << kq << endl;
    return 0;
}
Khuyên dùng

 

Speak Your Mind

*