VKNIGHTS – spoj

Đề bài:


Thuật toán:


  • Quy hoạch động trạng thái

Code:


#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 200;
const int oo = (1 << 6) - 1;
 
int n, x, ans1, f[MAXN][oo+3], a[5][MAXN], z[MAXN];
ll ans2, t[MAXN][oo+3];
 
bool getbit(int state, int i) {
    return (state >> (6-i) ) & 1;
}
 
int tinh(int state) {
    int res = 0;
    FOR(i,1,6)
    if (getbit(state,i)) res++;
    return res;
}
 
int main() {
    	ios_base::sync_with_stdio(0); cin.tie(0);
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> n;
    FOR(i,1,n) {
        cin >> x;
        if (x) a[x][i] = 1;
    }
    FOR(i,1,3) {
        z[1] = z[1] * 2 + a[i][1];
    }
    FOR(i,2,n) {
        FOR(j,1,3) z[i] = z[i] * 2 + a[j][i-1];
        FOR(j,1,3) z[i] = z[i] * 2 + a[j][i];
    }
    f[0][0] = 0; t[0][0] = 1;
    FOR(j,0,(1<<3)-1)
    if ((z[1]&j)==0) {
        f[1][j] = tinh(j);
        t[1][j] = 1;
    }
    FOR(i,2,n) {
        FOR(state,0,oo)
        if ((z[i]&state)==0)
        FOR(j,0,oo)
        if ((z[i-2]&j)==0)
        if (t[i-2][j]>0)
        if ((i>3||(i==2&j==0))||(i==3&j<(1<<3)))
        {
            // check ma
            bool ok = 1;
            if (getbit(state,1)) {
                if (getbit(state,6)) ok = 0;
                if (getbit(j,6)) ok = 0;
                if (getbit(j,2)) ok = 0;
            }
            if (getbit(state,2)) {
                if (getbit(j,1)) ok = 0;
                if (getbit(j,3)) ok = 0;
            }
            if (getbit(state,3)) {
                if (getbit(state,4)) ok = 0;
                if (getbit(j,2)) ok = 0;
                if (getbit(j,4)) ok = 0;
            }
            if (getbit(state,4)) {
                if (getbit(state,3)) ok = 0;
                if (getbit(j,5)) ok = 0;
            }
            if (getbit(state,5)) {
                if (getbit(j,4)) ok = 0;
                if (getbit(j,6)) ok = 0;
            }
            if (getbit(state,6)) {
                if (getbit(j,5)) ok = 0;
                if (getbit(state,1)) ok = 0;
            }
            // qhd
            if (ok)
            if (f[i][state]<f[i-2][j]+tinh(state)) {
                f[i][state] = f[i-2][j] + tinh(state);
                t[i][state] = t[i-2][j];
            }
                else
            if (f[i][state]==f[i-2][j]+tinh(state)) {
                t[i][state] += t[i-2][j];
            }
        }
    }
    FOR(state,0,oo) ans1 = max(ans1,f[n][state]);
    FOR(state,0,oo)
    if (f[n][state]==ans1) ans2 += t[n][state];
    cout << ans1 << " " << ans2;
	return 0;
}

LEM3 – spoj

Đề bài:

Thuật toán:

  • Đây là bài cơ bản của thuật toán quy hoạch động trạng thái.
  • Nếu giải bài này bằng duyệt sẽ không ăn được hết test.
  • Gọi F[i,state] là độ dài hành trình ngắn nhất khi đến được i và trạng thái thăm/chưa thăm các thành phố là state
    • state có dạng dãy bit 0,1. 1 là đã thăm, 0 là chưa thăm

Code:

Pascal (ideone)

uses    math;
const   fi='';
        fo='';
        maxn = 16;
        oo = 1 shl 16 -1;
var     f       :array[0..oo,1..maxn] of longint;
        i,j,n   :longint;
        c       :array[1..maxn,1..maxn] of longint;
        res     :longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do
                for j:=1 to n do read(c[i,j]);
        close(input);
end;
function getbit( i,x :longint):byte;
begin
        getbit := (x shr (i-1)) and 1;
end;
function turnoff( i,x   :longint):longint;
begin
        turnoff := x and not (1 shl (i-1));
end;
procedure process;
var     i,j,k,t,state   :longint;
begin
        t := 1 shl n -1;
        for i:= 0 to t do
                for j:=1 to n do
                        f[i,j] := trunc(1e9);
        for i := 0 to t do
                for j := 1 to n do
                        if getbit(j,i)=1 then
                        begin
                                state := turnoff(j,i);
                                if state = 0 then begin f[i,j] := 0; break; end;
                                for k:=1 to n do
                                        if getbit(k,i)=1 then
                                                f[i,j] := min(f[i,j], f[state,k] + c[k,j]);
                        end;
        res := trunc(1e9);
        for i:=1 to n do
                res := min(res, f[t,i]);
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

C++ (ideone)

#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = a; i <= b; i++)
#define ford(i, a, b) for (int i = a; i >= b; i--)
const int maxn = 1e5 ;
const int base = 1e9 + 7;
const int maxa = 1e6 * 5 + 1;
const int N = 50;
using namespace std;
int n,a[N][N],f[maxn][N],t[N],ans;
 
int get(int x,int i)
{
    return (x>>(i-1))&1;
}
 
int off(int x,int i)
{
    return x ^ (1<<(i-1));
}
 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    //freopen("trip.INP","r",stdin);
    //freopen("trip.OUT","w",stdout);
    cin>>n;
    fore(i,1,n)
    fore(j,1,n) cin>>a[i][j];
    int xx = (1<<n)-1;
    fore(x,1,xx)
    {
        int l = 0;
        fore(i,1,n)
        if (get(x,i)) t[++l] = i;
        if (l == 1) continue;
        fore(i,1,l)
        {
            int x1 = off(x,t[i]);
            f[x][t[i]] = base;
            fore(j,1,l)
            if (i != j && f[x][t[i]] > f[x1][t[j]] + a[t[j]][t[i]])
                f[x][t[i]] = f[x1][t[j]] + a[t[j]][t[i]];
            //if (x == 36)
                //cout<<t[i]<<' '<<f[x][t[i]]<<endl;
        }
    }
    ans = base;
    //cout<<get(36,1)<<endl;
    fore(i,1,n)
    ans = min(ans , f[xx][i]);
    cout<<ans;
    return 0;
}

QBSELECT – spoj

Đề bài: http://vn.spoj.com/problems/QBSELECT/

Tóm tắt đề bài: Cho bảng 4*n, chọn các ô không kề cạnh sao cho tổng các ô chọn lớn nhất

Ví dụ: Xét bảng với n=3 trong hình vẽ dưới đây:

qbselect-yeulaptrinh

 

Cách chọn cần tìm là tập các ô S = {(3,1), (1,2), (4,2), (3,3)} với trọng lượng 32.

Thuật toán:

–         Theo đề bài thì bảng có 4 dòng và n cột;

  • Gọi S là trạng thái chọn các ô ở cột thứ j, ta có thể biểu diễn S bằng 4 bit (các bit được đánh số từ phải sang bắt đầu bằng 0) với ý nghĩa:

+    S[i-1] = 0: dòng thứ i của cột j không được chọn;

+    S[i-1] =1: dòng thứ i của cột j được chọn.

  • Với 4 bit, S có thể biểu diễn 16 trạng thái từ {0000} đến {1111} (từ 0 đến 15), tuy nhiên ta nhận thấy chỉ có 8 trạng thái sau là thỏa yêu cầu của bài toán: {0000}, {0001}, {0010},

{0100}, {1000}, {1001}, {0101}, {1010} (tương ứng với các giá trị 0, 1, 2, 4, 5, 8, 9, 10).

  • Gọi T[S, j] là trọng lượng lớn nhất khi chọn các ô đến cột thứ j với trạng thái chọn là S, ta có công thức quy hoạch động như sau:

T[S, j] = max(T[P, j-1] + value(S))

với P là trạng thái của cột liền trước của S sao cho P và S không có 2 bit 1 đồng thời ở cùng vị trí, còn value (S) là giá trị cách chọn cột j với trạng thái S.

  • Khi cài đặt, với bài toán này, ta chỉ cần xây dựng hàm getBit để giải mã trạng thái S
  • Còn thao tác quy hoạch động được thực hiện bình thường

Code:

uses    math;
const   fi='';
        fo='';
        maxn=10000;
        s:array[1..8] of integer = (0,1,2,4,5,8,9,10);
var     t:array[0..maxn,1..8] of longint;
        i,j,k,n:integer;
        res,tam:longint;
        a:array[1..maxn,1..4] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);
 
    readln(n);
 
    for i:=1 to 4 do
        for j:=1 to n do read(a[j,i]);
 
    close(input);
end;
function getbit(x,y:integer):byte;
begin
    getbit:=(x shr y) and 1;
end;
procedure xuly;
begin
    for i:=1 to n do
        for j:=1 to 8 do
        begin
            tam:=0;
            for k:=1 to 4 do tam:=tam+getbit(s[j],k-1)*a[i,k];
            for k:=1 to 8 do
              if (s[j] and s[k]=0) and (t[i-1,k]+tam>t[i,j])
                then t[i,j]:=t[i-1,k]+tam;
        end;
 
    res:=low(longint);
    for i:=1 to 8 do res:=max(res,t[n,i]);
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
 
    tam:=low(integer);
    for i:=1 to n do
        for j:=1 to 4 do tam:=max(tam,a[i,j]);
 
    if tam<=0 then begin writeln(tam); halt; end;
 
    writeln(res);
 
    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
end.