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;
}

SEQ198 – spoj

Đề bài:

Thuật toán:

  • Sử dụng phương pháp quy hoạch động kết hợp với bitmask.
  • Sắp xếp lại mảng A.
  • f[i,state] là số phần tử cần loại bỏ của dãy A[1..i] khi có state là trạng thái giữ hoặc chọn của 10 số cuỗi của dãy.

Code:

#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)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define X first
#define Y second
#define ll long long
#define mp make_pair
#define pb push_back
#define endl '\n'
 
const int MAXN = 1e5 * 5;
const int inf = 1024;
const int N = 5000;
 
using namespace std;
int n,p[N],a[N],b[N],l[N],ans,ss,c[N],f[2001][1025];
 
void update()
{
    int cnt = 0;
    int dem = 0;
    FORE(i,1,min(n,10))
    if (l[i])
            c[++cnt] = a[i],dem += b[i];
    sort(c+1,c+cnt+1);
    FORE(i,1,cnt)
    FORD(j,i-1,1)
    if (c[i] - c[j] > 9) break;
    else
    {
        if (c[i] - c[j] == 1) return;
        if (c[i] - c[j] == 8) return;
        if (c[i] - c[j] == 9) return;
    }
    f[10][ss] = dem;
    ans = max(ans , dem);
}
 
void duyet(int i)
{
    FORE(j,0,1)
    {
        ss = ss*2 + j;
        l[i] = j;
        if (i == min(n,10)) update();
        else duyet(i+1);
        ss /= 2;
    }
}
 
int ok(int u,int v)
{
    if (u - v == 1) return 1;
    if (u - v == 8) return 1;
    if (u - v == 9) return 1;
    return 0;
}
 
int check(int s,int i)
{
    FORE(j,0,8)
    {
        int xx = (s >> j)&1;
        if (xx && ok(a[i],a[i - j - 1])) return 1;
    }
    return 0;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("", "r", stdin);
    freopen("", "w", stdout);
    #endif //yeulaptrinh.pw
    cin>>n;
    int lx = n;
    FORE(i,1,n) cin>>p[i];
    sort(p+1,p+n+1);
    int po = -1;
    int n1 = 0;
    FORE(i,1,n)
    if (p[i] != po)
    {
        po = p[i];
        ++n1;
        a[n1] = p[i];
        ++b[n1];
    }
    else ++b[n1];
    n = n1;
    duyet(1);
    if (n <= 10)
    {
        cout<<lx - ans;
        return 0;
    }
    FORE(i,10,n-1)
    FORE(x,0,1023)
    {
        int xx = (2*x)%inf;
        f[i+1][xx] = max(f[i+1][xx] , f[i][x]);
        if (check(x,i+1)) continue;
        xx = (2*x + 1)%inf;
        f[i+1][xx] = max(f[i+1][xx] , f[i][x] + b[i+1]);
    }
    int kq = 0;
    FORE(i,10,n)
    FORE(x,0,1024)
        kq = max(kq , f[i][x]);
    cout<<lx - kq;
    return 0;
}
uses math;
const
  fi = '';
var
  a,b,cnt : array[0..2001] of longint;
  f : array[0..2001,0..511] of longint;
  dd : array[0..2001,0..511] of boolean;
  n,n1 : longint;
 
procedure enter;
  var
    i : longint;
  begin
    assign(input,fi);
    reset(input);
    readln(n);
    for i := 1 to n do
      read(b[i]);
    close(input);
  end;
 
 
procedure qsort(l,r : longint);
  var
    i,j,k,tmp : longint;
  begin
    i := l;
    j := r;
    k := b[l + random(r - l + 1)];
    while i < j do
      begin
        while b[i] < k do inc(i);
        while b[j] > k do dec(j);
        if i <= j then
          begin
            tmp := b[i];
            b[i] := b[j];
            b[j] := tmp;
            inc(i);
            dec(j);
          end;
      end;
    if l < j then qsort(l,j);
    if i < r then qsort(i,r);
  end;
 
function getbit(x,i : longint) : longint;
  begin
   exit(1 and (x shr (i - 1)));
  end;
 
function check(stt : longint) : boolean;
  begin
    if (getbit(stt,1) = 1) or (getbit(stt,8) = 1) or (getbit(stt,9) = 1) then exit(false);
    exit(true);
  end;
 
function batbit(x,i : longint) : longint;
  begin
    exit(x or (1 shl (i - 1)));
  end;
 
function sttnext(tt,stt,i : longint) : longint;
  var
    res,kc,j : longint;
  begin
    kc := a[i+1] - a[i];
    res := 0;
    for j := 0 to 9 - kc do
      if j = 0 then
        begin
          if tt = 1 then res := batbit(res,kc)
        end
      else
        if getbit(stt,j) = 1 then
          res := batbit(res,kc + j);
    exit(res);
  end;
 
procedure init;
  var
    i,j : longint;
  begin
    qsort(1,n);
    a[1] := b[1];
    j := 1;
    cnt[1]:=1;
    for i := 2 to n do
      if b[i] <> a[j] then
        begin
          inc(j);
          a[j] := b[i];
          cnt[j] := 1;
        end
      else inc(cnt[j]);
    n1:=j;
    a[n1+1] := high(longint)
  end;
 
function cal(i,stt: longint) : longint;
  var
    ff : longint;
  begin
    if dd[i,stt] then exit(f[i,stt]);
    dd[i,stt] := true;
    if i = n1 + 1 then
      ff := 0
    else
      begin
        ff := cal(i + 1,sttnext(0,stt,i)) + cnt[i];
        if check(stt) then
          ff := min(ff,cal(i + 1,sttnext(1,stt,i)));
      end;
    f[i,stt] := ff;
    exit(ff);
  end;
 
procedure print;
  begin
    writeln(cal(1,0));
  end;
 
begin
  enter;
  init;
  print;
end.