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 flashmt

#include <iostream>
#include <algorithm>
using namespace std;
const int base = 1000000, digit = 6;

struct bignum
{
    int a[70], l;

    bignum()
    {
        l = 1;
        for (int i = 0; i < 70; i++) a[i] = 0;
    }

    bignum(int x)
    {
        for (int i = 0; i < 70; i++) a[i] = 0;
        l = 1;
        a[0] = x;
    }

    bignum operator + (bignum u)
    {
        bignum res;
        int mem = 0;
        res.l = max(l, u.l);
        for (int i = 0; i < res.l; i++)
        {
            res.a[i] = a[i] + u.a[i] + mem;
            if (res.a[i] >= base) res.a[i] -= base, mem = 1;
            else mem = 0;
        }
        if (mem) res.a[res.l++] = 1;
        return res;
    }

    bignum operator * (int x)
    {
        bignum res;
        int mem = 0;
        res.l = l;
        for (int i = 0; i < l; i++)
        {
            res.a[i] = a[i] * x + mem;
            mem = res.a[i] / base;
            res.a[i] %= base;
        }
        if (mem) res.a[res.l++] = mem;
        return res;
    }

    friend bignum max(bignum u, bignum v)
    {
        if (u.l > v.l) return u;
        if (u.l < v.l) return v;
        for (int i = u.l - 1; i >= 0; i--)
            if (u.a[i] > v.a[i]) return u;
            else 
                if (u.a[i] < v.a[i]) return v;
        return u;
    }

    int isPositive()
    {
        return l > 1 || a[l - 1];
    }       

    int len(int x)
    {
        return !x ? 0 : len(x / 10) + 1;
    }

    void write()
    {
        for (int i = l - 1; i >= 0; i--)
        {
            if (i < l - 1)
                for (int j = max(len(a[i]), 1); j < digit; j++) 
                    cout << 0;
            cout << a[i];
        }
        cout << endl;
    }
};

bignum f[222][222], F[222], g[222][222];
int n, s, w, m, bMin, bMax;
long long h[222];

void calcF()
{
    f[0][0] = bignum(1);
    for (int i = 1; i <= 200; i++)
        for (int j = 0; j < i; j++)
        {
            f[i][j] = f[i - 1][j] * (j + 1);
            if (j) f[i][j] = f[i][j] + f[i - 1][j - 1] * (i - j);
        }
}

int main()
{
    calcF();

    int test, x;
    cin >> test;
    while (test--)
    {
        cin >> n >> s >> w >> m >> bMin >> bMax;
        w = min(w, n - 1);
        for (int i = 1; i <= n; i++) cin >> x, h[i] = h[i - 1] + x;

        for (int i = 1; i <= n; i++)
        {
            F[i] = bignum(0);
            for (int j = 0; j <= w; j++) F[i] = F[i] + f[i][j];
        }

        g[0][0] = bignum(1);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= s; j++)
            {
                g[i][j] = bignum(0);
                for (int ii = 0; ii < i; ii++)
                    if ((h[i] - h[ii]) * m >= bMin && (h[i] - h[ii]) * m <= bMax && g[ii][j - 1].isPositive())
                        g[i][j] = max(g[i][j], g[ii][j - 1] + F[i - ii]);
            }

        g[n][s].a[0]--;
        g[n][s].write();
    }
}

Code mẫu của happyboy99x

#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;

template<class T> void checkMax(T &a, const T &b) {
    if(a < b) a = b;
}

struct BigInteger {
    static const int MAX_LEN = 60, BASE = 1e7;
    int d[MAX_LEN], n;

    BigInteger(int x = 0) {
        assign(x);
    }

    void assign(int x) {
        n = 0; memset(d, 0, sizeof d);
        for(; x > 0; x /= BASE)
            d[n++] = x % BASE;
    }

    void fix() {
        int rem = 0;
        for(int i = 0; i < n; ++i) {
            int t = d[i] + rem;
            d[i] = t % BASE;
            rem = t / BASE;
        }
        for(; rem > 0; rem /= BASE)
            d[n++] = rem % BASE;
    }

    bool operator < (const BigInteger &a) const {
        if(n != a.n) return n < a.n;
        for(int i = n - 1; i >= 0; --i)
            if(d[i] != a[i]) return d[i] < a[i];
        return false;
    }

    void operator += (const BigInteger &a) {
        n = max(n, a.n);
        for(int i = 0; i < n; ++i) d[i] += a[i];
        fix();
    }

    BigInteger operator + (BigInteger a) const {
        a += *this;
        return a;
    }

    BigInteger operator * (int x) const {
        BigInteger res = *this;
        for(int i = 0; i < res.n; ++i) res[i] *= x;
        return res.fix(), res;
    }

    int operator [] (int p) const {
        return d[p];
    }

    int& operator [] (int p) {
        return d[p];
    }
};

ostream& operator << (ostream& out, const BigInteger &a) {
    if(a.n == 0) out << 0;
    else {
        out << a[a.n - 1];
        for(int i = a.n - 2; i >= 0; --i)
            out << setfill('0') << setw(7) << a[i];
    }
    return out;
}

const int N = 200;
BigInteger g[N + 1][N + 1], f[N + 1][N + 1];
int n, s, w, m, bmin, bmax, h[N];

void firstDP() {
    g[1][0].assign(1);
    for(int i = 1; i < N; ++i)
        for(int j = 0; j < i; ++j) {
            g[i + 1][j] += g[i][j] * (j + 1);
            g[i + 1][j + 1] += g[i][j] * (i - j);
        }
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            g[i][j] += g[i][j - 1];
}

void secondDP() {
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < s; ++j) if((i | j) == 0 || f[i][j].n > 0) {
            int weight = 0;
            for(int k = i; k < n; ++k) {
                weight += h[k] * m;
                if(weight > bmax) break;
                if(weight >= bmin)
                    checkMax(f[k + 1][j + 1], f[i][j] + g[k - i + 1][w]);
            }
        }
}

void enter() {
    cin >> n >> s >> w >> m >> bmin >> bmax;
    for(int i = 0; i < n; ++i) cin >> h[i];
}

int main() {
    ios::sync_with_stdio(false);
    int tc; cin >> tc;
    firstDP();
    while(tc--) {
        memset(f, 0, sizeof f);
        enter();
        secondDP();
        cout << f[n][s] << '\n';
    }
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#include <climits>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>

const int N = 222;
const int BASE = 1000000;
const int LEN = 6;

using namespace std;

//BEGIN OF BIGNUM

typedef VI big;

bool operator < (big &a, big &b) {
    if (SZ(a) != SZ(b)) return SZ(a) < SZ(b);
    REPD(i, SZ(a) - 1, 0) if (a[i] != b[i]) return a[i] < b[i];
    return 0;
}

void fix(big &a) {
    a.PB(0);
    FOR(i, 0, SZ(a) - 1) {
        a[i + 1] += a[i] / BASE; a[i] %= BASE;
        if (a[i] < 0) {a[i] += BASE; a[i + 1]--;}
    }
    while (SZ(a) > 1 && a.back() == 0) a.pop_back();
}

void operator += (big &a, big b) {
    a.resize(max(SZ(a), SZ(b)));
    FOR(i, 0, SZ(b)) a[i] += b[i];
    fix(a);
}
big operator + (big a, big &b) {a += b; return a;}

void operator *= (big &a, int b)
    {FOR(i, 0, SZ(a)) a[i] *= b; fix(a);}
big operator * (big a, int b) {a *= b; return a;}

ostream& operator << (ostream& cout, const big &a) {
    if (a.empty()) cout << 0;
    else {
        printf("%d", a.back());
        REPD(i, SZ(a) - 2, 0) printf("%06d", a[i]);
    }
    return cout;
}
//END OF BIGNUM

int n, nPart, nCon, mul, bMin, bMax;
int h[N];
big g[N][N], cnt[N], f[N][N];
bool was[N][N];

void maxi(big &a, big b) {if (a < b) a = b;}

void readInput() {
    cin >> n >> nPart >> nCon >> mul >> bMin >> bMax;
    REP(i, 1, n) cin >> h[i];
}

void resetData() {
    REP(i, 0, n) {
        cnt[i].clear();
        REP(j, 0, nCon)
            g[i][j].clear();
    }
    REP(i, 0, n) REP(j, 0, nPart) {
        was[i][j] = 0;
        f[i][j].clear();
    }
}

void preProcess() {
    g[0][0] = cnt[0] = big(1, 1);
    REP(i, 1, n) FOR(j, 0, min(i, nCon + 1)) {
        g[i][j] = g[i - 1][j] * (j + 1);
        if (j > 0) g[i][j] += g[i - 1][j - 1] * (i - j);
        cnt[i] += g[i][j];
    }
}

void solve() {
    was[0][0] = 1; f[0][0].PB(0);
    REP(i, 1, n) REP(j, 1, min(i, nPart)) {
        LL sumWeight = 0;
        REPD(k, i - 1, 0) {
            sumWeight += h[k + 1] * mul;
            if (sumWeight > bMax) break;
            if (bMin <= sumWeight && was[k][j - 1]) {
                maxi(f[i][j], f[k][j - 1] + cnt[i - k]);
                was[i][j] = 1;
            }
        }
    }
    cout << f[n][nPart] << '\n';
}

int main() {
    int nTest;
    cin >> nTest;
    while (nTest--) {
        readInput();
        resetData();
        preProcess();
        solve();
    }
    return 0;
}

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#define MAX   211
#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)
using namespace std;
const int base=(int)1e4;
struct Bignum {
    vector<int> dig;
    Bignum() {
        dig.clear();
    }
    Bignum(long long x) {
        dig.clear();
        if (x==0) dig.push_back(0);
        while (x>0) {
            dig.push_back(x%base);
            x/=base;
        }
    }
    Bignum operator + (const Bignum &x) const {
        Bignum res;
        int rem=0;
        REP(i,max(dig.size(),x.dig.size())) {
            int a=i<dig.size()?dig[i]:0;
            int b=i<x.dig.size()?x.dig[i]:0;
            res.dig.push_back((a+b+rem)%base);
            rem=(a+b+rem)/base;
        }
        while (rem>0) {
            res.dig.push_back(rem%base);
            rem/=base;
        }
        while (res.dig.size()>1 && res.dig.back()==0) res.dig.pop_back();
        return (res);
    }
    void operator += (const Bignum &x) {
        *this=*this+x;
    }
    Bignum operator * (const Bignum &x) const {
        Bignum res(0);
        REP(i,x.dig.size()) {
            Bignum tmp;
            int rem=0;
            REP(j,i) tmp.dig.push_back(0);
            REP(j,dig.size()) {
                tmp.dig.push_back((x.dig[i]*dig[j]+rem)%base);
                rem=(x.dig[i]*dig[j]+rem)/base;
            }
            while (rem>0) {
                tmp.dig.push_back(rem%base);
                rem/=base;
            }
            while (tmp.dig.size()>1 && tmp.dig.back()==0) tmp.dig.pop_back();
            res+=tmp;
        }
        return (res);
    }
    bool operator < (const Bignum &x) const {
        if (dig.size()!=x.dig.size()) return (dig.size()<x.dig.size());
        FORD(i,(int)dig.size()-1,0) if (dig[i]!=x.dig[i]) return (dig[i]<x.dig[i]);
        return (false);
    }
    bool operator > (const Bignum &x) const {
        return (x<*this);
    }
    bool operator == (const Bignum &x) const {
        return (!(x<*this) && !(*this<x));
    }
    void print(void) const {
        printf("%d",dig.back());
        FORD(i,(int)dig.size()-2,0) printf("%04d",dig[i]);
        printf("\n");
    }
};
Bignum countWay[MAX+7][MAX+7];
void precount(void) {
    REP(i,MAX+7) REP(j,MAX+7) countWay[i][j]=Bignum(0);
    countWay[1][0]=1;
    FOR(i,1,MAX) REP(j,i) if (countWay[i][j]>Bignum(0)) {
        countWay[i+1][j+1]+=countWay[i][j]*Bignum(i-j);
        countWay[i+1][j]+=countWay[i][j]*Bignum(j+1);
    }
}
int n,nSeg,limPos,mul,minSum,maxSum;
int h[MAX],sumH[MAX];
Bignum nWay[MAX];
Bignum f[MAX][MAX];
bool ok[MAX][MAX];
void maximize(Bignum &x,const Bignum &y) {
    if (x<y) x=y;
}
void init(void) {
    scanf("%d%d%d%d%d%d",&n,&nSeg,&limPos,&mul,&minSum,&maxSum);
    FOR(i,1,n) {
        scanf("%d",&h[i]);
        sumH[i]=sumH[i-1]+h[i];
    }
    if (minSum%mul==0) minSum=minSum/mul; else minSum=minSum/mul+1;
    maxSum=maxSum/mul;
}
void process(void) {
    FOR(i,1,n) nWay[i]=Bignum(0);
    FOR(i,1,n) REP(j,i) if (j<=limPos) nWay[i]+=countWay[i][j];
    REP(i,n+1) REP(j,nSeg+1) f[i][j]=Bignum(0);
    REP(i,n+1) REP(j,nSeg+1) ok[i][j]=false;
    ok[0][0]=true;
    REP(i,n) REP(j,nSeg) if (ok[i][j]) FOR(k,i+1,n) {
        if (sumH[k]-sumH[i]>maxSum) break;
        if (sumH[k]-sumH[i]<minSum) continue;
        ok[k][j+1]=true;
        maximize(f[k][j+1],f[i][j]+nWay[k-i]);
    }
    f[n][nSeg].print();
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif // ONLINE_JUDGE
    precount();
    int t;
    scanf("%d",&t);
    REP(zz,t) {
        init();
        process();
    }
    return 0;
}