Editorial for VOI 16 Bài 1 - SEQ198


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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 skyvn97

#include<bits/stdc++.h>
#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 fi   first
#define se   second
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X,class Y>
    void minimize(X &x,const Y &y) {
        if (x>y) x=y;
    }
template<class X,class Y>
    void maximize(X &x,const Y &y) {
        if (x<y) x=y;
    }
template<class T>
    T Abs(const T &x) {
        return (x<0?-x:x);
    }

/* Author: Van Hanh Pham - skyvn97 */

/** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/

#define MAX   2222
const int INF = (int)1e9 + 7;

const int badMask = MASK(1) | MASK(8) | MASK(9);

map<int, int> cnt;

vector<pair<int, int> > values;
int n;
int f[MAX][MASK(10) + 7];

void init(void) {
    scanf("%d", &n);
    REP(love, n) {
        int x; scanf("%d", &x);
        cnt[x]++;
    }

    values = vector<pair<int, int> >(ALL(cnt));
    n = values.size();
}

void optimize(void) {
    memset(f, 0x3f, sizeof f);
    f[0][0] = values[0].se;
    f[0][MASK(0)] = 0;

    REP(i, n - 1) REP(j, MASK(10)) if (f[i][j] < INF) {
        int prev = values[i].fi;
        int cur = values[i + 1].fi;
        int newMask = cur - prev >= 10 ? 0 : ((1LL * j) << (cur - prev)) & (MASK(10) - 1);

        minimize(f[i + 1][newMask], f[i][j] + values[i + 1].se);
        if ((newMask & badMask) == 0) minimize(f[i + 1][newMask | MASK(0)], f[i][j]);
    }

    int res = INF;
    REP(j, MASK(10)) minimize(res, f[n - 1][j]);
    printf("%d\n", res);
}

int main(void) {
    init();
    optimize();
    return 0;
}

/*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/

Comments

Please read the guidelines before commenting.


There are no comments at the moment.