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.
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