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>
#define fr(a,b,c) for(a=b;a<=c;a++)
#define maxn 100100
using namespace std;
typedef long long ll;

int n,k,z,q[maxn],a[maxn];
ll e[maxn],f[maxn][11],g[maxn];

ll c(int j,int i)
{
    return e[i]-e[j]-1LL*(a[i]-a[j])*(j+1);
}

int cmp(int j,int k,int val)
{
    return g[j]-g[k]<=1LL*val*(j-k);
}

int cmpp(int i,int j,int k)
{
    return (g[i]-g[j])*(j-k)<=(g[j]-g[k])*(i-j);
}

int main()
{
    int i,j,x;
    cin >> n >> k;
    fr(i,1,n)
    {
       scanf("%d",&x);
       a[i]=a[i-1]+x;
       e[i]=e[i-1]+x*i;      
       f[i][1]=f[i-1][1]+x*(i-1);
    }
    fr(z,2,k)
    {
       int low=1,high=1;
       q[1]=1;
       g[1]=a[1];
       fr(i,2,n)
       {
          while (high-low && cmp(q[low+1],q[low],a[i])) low++;
          f[i][z]=f[q[low]][z-1]+c(q[low],i);
          g[i]=f[i][z-1]-e[i]+1LL*a[i]*(i+1);
          while (high-low && cmpp(i,q[high],q[high-1])) high--;
          q[++high]=i;
       }            
    }
    cout << f[n][k] << endl;      
    return 0;
}

Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
#include<cstdio>
using namespace std;

template<class T> int size(const T &a) {
    return a.size();
}

long long roundDown(long long x, long long y) {
    if(y < 0) x = -x, y = -y;
    if(x > 0) return x / y;
    return (x - y + 1) / y;
}

struct Line {
    long long a, b, lim;

    long long getIntersectX(const Line &d) const {
        return roundDown(b - d.b, d.a - a);
    }

    long long getY(long long x) {
        return a * x + b;
    }

    Line(long long a, long long b, long long lim):
        a (a), b (b), lim (lim) {}
};

void addLine(vector<Line> &v, const Line &d) {
    int n = size(v);
    while(n >= 2 && d.getIntersectX(v[n - 1]) <= d.getIntersectX(v[n - 2]))
        v.pop_back(), --n;
    if(n > 0) v.back().lim = d.getIntersectX(v.back());
    v.push_back(d);
}

const int N = 1e5;
const long long INF = 1e15;
long long sigma[N], f[N], g[N];
int n, k, w[N], s[N];

void enter() {
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> w[i];
}

void init() {
    sigma[0] = 0;
    for(int i = 1; i < n; ++i) sigma[i] = sigma[i - 1] + i * w[i];
    partial_sum(w, w + n, s);
}

void solve() {
    copy(sigma, sigma + n, f);
    for(int t = 2; t <= k; ++t) {
        copy(f, f + n, g);
        vector<Line> v;
        for(int i = 0, p = 0; i < n; ++i) {
            if(v.empty()) f[i] = INF;
            else {
                while(s[i] > v[p].lim) ++p;
                f[i] = v[p].getY(s[i]) + sigma[i];
            }
            addLine(v, Line(-(i + 1), g[i] - sigma[i] + s[i] * (i + 1LL), INF));
        }
    }
    cout << f[n - 1] << endl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    enter();
    init();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 100005;
const long long oo = 1000000000000000000ll;
using namespace std;
long long w[N], s[N], ss[N];
long long F[2][N];
int n, hole, Q[N];

long long Cost(int& i, int& j) {
    return (j - i - 1) * s[i] + ss[j] - ss[i+1];
}

long long g(int& j, int& k, int t) {
    return (F[t][j] - F[t][k] + ss[j] - ss[k]) / (k - j);
}

int main()
{
    scanf("%d %d", &n, &hole);
    int i, j, k;
    for(i=1; i<=n; i++) scanf("%d", &w[n - i + 1]);
    for(i=n; i; i--) {s[i] = s[i + 1] + w[i]; ss[i] = ss[i + 1] + s[i];}
    int now = 1, prev = 0;
    for(i=1; i<=n; i++) F[prev][i] = oo;

    int l, r;
    for(j=1; j<=hole; j++) {
        l = r = 1; Q[1] = n + 1; F[now][n + 1] = oo;
        for(i=n; i; i--) {
            while (l < r && g(Q[l + 1], Q[l], prev) <= s[i]) l++;
            F[now][i] = F[prev][Q[l]] + Cost(i, Q[l]);
            while (l < r && g(i, Q[r], prev) <= g(Q[r], Q[r - 1], prev)) r--;
            Q[++r] = i;
        }
        swap(now, prev);
    }
    cout << F[prev][1];
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>

#define MAXN 100111
#define oo 10001110001110LL
#define MAXK 11
#define FOR(i,a,b)  for(long i=a; i<=b; i++)
#define FORD(i,a,b) for(long i=a; i>=b; i--)
#define PB push_back
#define PF push_front
using namespace std;

long debug=0;
long n,k,w[MAXN];
long long s[MAXN],p[MAXN],sp[MAXN],f[MAXK][MAXN];
long q[MAXN],front,back;

void inp() {
    scanf("%ld %ld",&n,&k);
    FORD(i,n,1) scanf("%ld",&w[i]);
}

inline long long g(long k,long l,long j) {
    return f[j-1][k+1] - f[j-1][l+1] + sp[l] - sp[k]; 
}

inline long long c(long i,long j) {
    return j*(s[i]-s[j+1])-p[i]+p[j+1];
}

void solve() {
    FORD(i,n,1) s[i]=s[i+1]+w[i];
    FORD(i,n,1) p[i]=p[i+1]+i*w[i];
    FOR(i,1,n)  sp[i]=i*s[i+1]-p[i+1];

    FOR(i,1,n) f[1][i]=n*s[i]-p[i];

    FOR(j,2,k) {
        front=1; back=0;
        q[++back]=n+1-j;

        FORD(i,n-j,1) {
            while (front<back && g(q[front+1],q[front],j)<=s[i]*(q[front]-q[front+1])) front++;

            f[j][i]=f[j-1][q[front]+1]+c(i,q[front]);

            while (front<back
              && g(i,q[back],j) * (q[back-1]-q[back])
              <= g(q[back],q[back-1],j) * (q[back]-i) ) back--;

            q[++back]=i;
            f[j][i]<?=f[j-1][i+1];            
        }
    }

    cout<<f[k][1]<<endl;
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    inp();
    solve();
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

typedef pair<int, int> II;

const double PI = acos(-1.0);
const double eps = 1e-9;

const int dr[] = {-1, 0, +1, 0};
const int dc[] = {0, +1, 0, -1};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e17 + 5;
const ll mod = (ll)1e9 + 7;

#define maxn 100005

int n, K;
int x[maxn], w[maxn];
ll s[maxn], p[maxn], F[12][maxn];
int front, back, que[maxn * 2];

void upmin(ll &u, ll v){
    u = min(u, v);
}

ll func(int level, int k, int l) {
    return F[level][k + 1] - F[level][l + 1] + x[l] * s[l + 1] - x[k] * s[k + 1] - p[l + 1] + p[k + 1];
}

// g(k, l) <= f(i)
bool isWorse1(int level, int k, int l, int i) {
    return func(level, k, l) <= (x[l] - x[k]) * s[i];
}

// g(j, k) <= g(k, l)
bool isWorse2(int level, int j, int k, int l) {
    return func(level, j, k) * (x[l] - x[k]) <= func(level, k, l) * (x[k] - x[j]);
}

ll cost(int i, int j) {
    return (ll)x[j] * (s[i] - s[j + 1]) + p[j + 1] - p[i];
}

ll doit() {
    s[n + 1] = p[n + 1] = 0;
    Ford(i, n, 1) {
        s[i] = s[i + 1] + w[i];
        p[i] = p[i + 1] + (ll)x[i] * w[i];
    }
    F[1][n + 1] = 0;
    For(i, 1, n) F[1][i] = cost(i, n);
    int level = 1;
    For(step, 2, K) {
        level ^= 1;
        For(i, 1, n + 1) F[level][i] = F[level ^ 1][i];
        front = back = 1; que[1] = n;
        Ford(i, n - 1, 1) {
            while (front + 1 <= back && isWorse2(level ^ 1, i, que[back], que[back - 1])) --back;
            que[++back] = i;
            while (front + 1 <= back && isWorse1(level ^ 1, que[front + 1], que[front], i)) ++front;
            int j = que[front];
            upmin(F[level][i], F[level ^ 1][j + 1] + cost(i, j));
        }
    }
    return F[level][1];
}


int main(){
//    freopen("in.txt", "r", stdin);

    cin >> n >> K;
    For(i, 1, n){
        scanf("%d", &w[n + 1 - i]);
        x[i] = i;
    }
    cout << doit() << endl;
    return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAXN   100100
#define MAXK   11
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define fi   first
#define se   second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll INF=(ll)1e18+7LL;
ll ceil(ll a,ll b) {
    if (b<0) return (ceil(-a,-b));
    if (a<0) return (-(-a)/b);
    return (a/b+(a%b>0));
}
class ConvexHull {
    private:
    struct segment {
       ll x,a,b;
        segment() {
            x=0;a=0;b=0;
        }
        segment(ll _x,ll _a,ll _b) {
            x=_x;a=_a;b=_b;
        }
        ll value(void) const {
            return (a*x+b);
        }
    };
    int nl,f,l;
    ll L,R;
    ii prev;
    vector<segment> v;
    public:
    ConvexHull() {
        L=0;R=0;nl=0;f=0;l=0;
    }
    ConvexHull(ll L,ll R,int n) {
        this->L=L;
        this->R=R;
        nl=0;f=0;l=0;
        v=vector<segment>(2*n+7);
    }
    void reset(void) {
        nl=0;
    }
    void addline(ll a,ll b) {
        nl++;
        if (nl<2) {
            f=0;l=1;
            v[0]=segment(L,a,b);
            v[1]=segment(R,a,b);
            prev=ii(a,b);
            return;
        }
        if (ii(a,b)<prev) return; else prev=ii(a,b);
        int i;
        for (i=l;i>=f;i=i-1) if (v[i].value()>a*v[i].x+b) break;
        if (i==l) return;
        if (i<f) {
            f=0;l=1;
            v[0]=segment(L,a,b);
            v[1]=segment(R,a,b);
            return;
        }
        ll x=ceil(v[i].b-b,a-v[i].a);
        v[i+1]=segment(x,a,b);
        v[i+2]=segment(R,a,b);
        l=i+2;
    }
    ll getmax(ll x) {
        while (f<l && v[f+1].x<=x) f++;
        return (v[f].a*x+v[f].b);
    }
};
ConvexHull CH;
int w[MAXN];
ll s[MAXN];
ll f[MAXN][MAXK];
int n,k;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&k);
    FOR(i,1,n) scanf("%d",&w[i]);
    FORD(i,n,1) s[i]=s[i+1]+w[i];
    CH=ConvexHull(-s[1]-7,7,n);
}
void optimize(void) {
    FOR(j,1,k-1) {
        CH.reset();
        FOR(i,j+1,n) {
            CH.addline(i-1,f[i-1][j-1]);
            f[i][j]=CH.getmax(-s[i])+s[i]*i;
        }
    }
    ll res=-INF;
    FOR(i,k,n) if (res<f[i][k-1]) res=f[i][k-1];
    res=-res;
    FOR(i,1,n) res+=1LL*w[i]*(i-1);
    printf("%lld",res);
}
int main(void) {
    init();
    optimize();
    return 0;
}