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;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*