头像

LoneBaleine


访客:1187

离线:13小时前


活动打卡代码 AcWing 293. 开车旅行

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define pb push_back
#define mk make_pair
#define sz(x) (int)(x).size()
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL mod = 1e9 + 7;
const int N = 1e5 + 50;

int n, m, x;
int h[N];
set<int>se;
map<int, int>mp;
vector<int>to[N];
int f[19][N][4], da[19][N][4], db[19][N][4], la, lb, x0;

void cal(int s, int x) {
    int p = s;
    la = lb = 0;
    for(ri i = 18; i >= 0; --i) {
        if(f[i][p][0] && la + lb + da[i][p][0] + db[i][p][0] <= x) {
            la += da[i][p][0];
            lb += db[i][p][0];
            p = f[i][p][0];
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(n);
    for(ri i = 1; i <= n; ++i) {
        read(h[i]);
        mp[h[i]] = i;
        se.insert(h[i]);
    }
    for(ri i = 1; i <= n; ++i) {
        auto it = se.lower_bound(h[i]);
        auto rit = it;
        auto end = se.end();
        end--;
        int cnt = 0;
        while(cnt < 2) {
            ++it;
            ++cnt;
            if(it == end) {
                break;
            }
        }
        cnt = 0;
        while(cnt < 2) {
            if(rit == se.begin()) {
                break;
            }
            --rit;
            ++cnt;
            if(rit == se.begin()) {
                break;
            }
        }
        vector<int>tmp;
        while(1) {
            if(rit == se.end()) {
                break;
            }
            if(*rit == h[i]) {
                ++rit;
                continue;
            }
            tmp.pb(*rit);
            if(rit == it) {
                break;
            }
            ++rit;
        }
        se.erase(h[i]);
        sort(tmp.begin(), tmp.end());
        int minn = INF, cminn = INF, p1 = INF, p2 = INF;
        for(auto x : tmp) {
            int delta = abs(x - h[i]);
            if(minn > delta) {
                cminn = minn;
                minn = delta;
                p2 = p1;
                p1 = x;
            } else if(minn == delta) {
                cminn = minn;
                minn = delta;
                int rr = p1;
                p1 = min(x, p1);
                p2 = max(x, rr);
            } else {
                if(delta < cminn) {
                    cminn = delta;
                    p2 = x;
                } else if(delta == cminn) {
                    p2 = min(p2, x);
                }
            }
        }
        to[i].pb(0), to[i].pb(0);
        if(p1 != INF) {
            to[i][0] = mp[p1];
        } 
        if(p2 != INF) {
            to[i][1] = mp[p2];
        }
    }
    /*for(ri i = 1; i <= n; ++i) {
        write(to[i][0], to[i][1]), LF;
    }*/
    for(ri i = 1; i <= n; ++i) {
        f[0][i][0] = to[i][1];
        f[0][i][1] = to[i][0];
        da[0][i][0] = abs(h[i] - h[to[i][1]]);
        db[0][i][1] = abs(h[i] - h[to[i][0]]);
    }
    for(ri i = 1; i < 18; ++i) {
        for(ri j = n; j >= 1; --j) {
            for(ri k = 0; k < 2; ++k) {
                if(i == 1) {
                    f[i][j][k] = f[i-1][f[i-1][j][k]][k^1];
                    da[i][j][k] = da[i-1][j][k] + da[i-1][f[i-1][j][k]][k^1];
                    db[i][j][k] = db[i-1][j][k] + db[i-1][f[i-1][j][k]][k^1];
                } else {
                    f[i][j][k] = f[i-1][f[i-1][j][k]][k];
                    da[i][j][k] = da[i-1][j][k] + da[i-1][f[i-1][j][k]][k];
                    db[i][j][k] = db[i-1][j][k] + db[i-1][f[i-1][j][k]][k];
                }
            }
        }
    }
    read(x0);
    double ans = 1e18, nowans;
    int ansid = 0;
    for(ri i = 1; i <= n; ++i) {
        cal(i, x0);
        //write(la, lb), LF;
        nowans = 1.0 * la / (1.0 * lb);
        //cout << ans << ' ' << nowans << endl;
        if(nowans < ans) {
            ans = nowans;
            ansid = i;
        } else if(nowans == ans && h[ansid] < h[i]){
            ansid = i;
        }
    }
    write(ansid), LF;
    read(m);
    int ts, tx;
    for(ri i = 1; i <= m; ++i) {
        read(ts, tx);
        cal(ts, tx);
        write(la, lb), LF;
    }
    return 0;
}


活动打卡代码 AcWing 240. 食物链

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define eb emplace_back
#define mk make_pair
#define sz(x) (int)x.size()
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL MOD = 1e9 + 7;
const int N = 5e4 + 50;

int f[N], d[N];

int Find(int x) {
    if(x == f[x]) {
        return x;
    }
    int t = f[x];
    f[x] = Find(f[x]);
    d[x] = (d[t] + d[x]) % 3;
    return f[x];
}

int n, k, x, y, ans;

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(n, k);
    for(ri i = 1; i <= n; ++i) {
        f[i] = i, d[i] = 0;
    }
    int op, u, v;
    for(ri i = 1; i <= k; ++i) {
        read(op, u, v);
        if(u > n || v > n) {
            ++ans;
            continue;
        }
        int fu = Find(u), fv = Find(v);
        if(fu != fv) {
            if(op == 1) {
                f[fu] = fv;
                d[fu] = ((3 - d[u]) % 3 + d[v]) % 3;
            } else {
                f[fu] = fv;
                d[fu] = (((3 - d[u]) % 3 + 1) % 3 + d[v] ) % 3;
            }
        } else {
            if(op == 1) {
                if(d[u] != d[v]) {
                    ++ans;
                }
            } else {
                if((d[u] - d[v] + 3) % 3 != 1) {
                    ++ans;
                }
            }
        }
    }
    write(ans), LF;
    return 0;
}


活动打卡代码 AcWing 296. 清理班次2

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define pb push_back
#define mk make_pair
#define sz(x) (int)(x).size()
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL mod = 1e9 + 7;
const int N = 1e5 + 50;

struct SEG {
    int ls[N<<2], rs[N<<2];
    LL f[N<<2];
    void pushup(int rt) {
        f[rt] = min(f[rt<<1], f[rt<<1|1]);
    }
    void build(int rt, int l, int r) {
        ls[rt] = l, rs[rt] = r, f[rt] = INF;
        if(l == r) {
            return ;
        }
        int mid = (l + r) >> 1;
        build(rt << 1 , l, mid);
        build(rt << 1 | 1 , mid + 1, r);
    }
    void change(int rt, int p, LL x) {
        if(ls[rt] == p && rs[rt] == p) {
            f[rt] = x;
            return ;
        }
        int mid = (ls[rt] + rs[rt]) >> 1;
        if(p <= mid) {
            change(rt << 1, p, x);
        } else {
            change(rt << 1 | 1, p, x);
        }
        pushup(rt);
    }
    LL query(int rt, int l, int r) {
        if(ls[rt] >= l && rs[rt] <= r) {
            return f[rt];
        }
        int mid = (ls[rt] + rs[rt]) >> 1;
        LL res = INF;
        if(l <= mid) {
            res = min(res, query(rt << 1, l, r));
        }   
        if(r > mid) {
            res = min(res, query(rt << 1 | 1, l, r));
        }
        return res;
    }
}seg;

vector<pair<int, LL>>v[N];
int n, m, e;

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(n, m, e);
    int delta = 2 - m;
    m += delta;
    e += delta;
    for(ri i = 1; i <= n; ++i) {
        int l, r;
        LL c;
        read(l, r, c);
        l += delta;
        r += delta;
        v[r].pb(mk(l, c));
    }
    seg.build(1, 1, e);
    seg.change(1, 1, 0);
    //write(seg.query(1, 1, 5));
    for(ri i = m; i <= e; ++i) {
        LL tmp = 1e18;
        for(auto x : v[i]) {
            //write(seg.query(1, x - 1, i)), LF;
            tmp = min(tmp, seg.query(1, x.first - 1, i) + x.second);
        }
        if(tmp != INF) {
            seg.change(1, i, tmp);
        }  
    }
    int ans = seg.query(1, e, e);
    if(ans == INF) {
        write(-1);
    } else {
        write(ans);
    }
    LF;
    return 0;
}


活动打卡代码 AcWing 297. 赤壁之战

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define pb push_back
#define mk make_pair
#define sz(x) (int)(x).size()
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL mod = 1e9 + 7;
const int N = 1e3 + 50;

int T, n, m, a[N];
LL f[N][N];
vector<int>v;

struct BIT{
    LL c[N];
    void init() {
        mem(c, 0);
    }
    int lowbit(int x) {
        return x & (-x);
    }
    void add(int p, LL x) {
        while(p < N) {
            c[p] += x;
            p += lowbit(p);
        }
    }
    LL getsum(int p) {
        LL sum = 0;
        while(p > 0) {
            sum = (sum + (c[p])) % mod;
            p -= lowbit(p);
        }
        return sum;
    }
}bit[N];

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(T);
    int kase = 0;
    while(T--) {
        read(n, m);
        for(ri i = 1; i <= m; ++i) {
            bit[i].init();
        }
        mem(f, 0);
        v.clear();
        for(ri i = 1; i <= n; ++i) {
            read(a[i]);
            v.pb(a[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        for(ri i = 1; i <= n; ++i) {
            a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        }
        f[1][1] = 1;
        bit[1].add(a[1], f[1][1]);
        for(ri i = 2; i <= n; ++i) {
            f[i][1] = 1;
            bit[1].add(a[i], f[i][1]);
            for(ri j = 2; j <= m; ++j) {
                f[i][j] = bit[j-1].getsum(a[i] - 1);
                bit[j].add(a[i], f[i][j]);
            }
        }
        /*for(ri i = 1; i <= n; ++i) {
            for(ri j = 1; j <= m; ++j) {
                write(f[i][j]), SP;
            }
            LF;
        }*/
        printf("Case #%d: ", ++kase);
        LL ans = 0;
        for(ri i = 1; i <= n; ++i) {
            ans += f[i][m];
            ans %= mod;
        }
        write(ans), LF;
    }
    return 0;
}


活动打卡代码 AcWing 295. 清理班次

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define pb push_back
#define mk make_pair
#define sz(x) (int)(x).size()
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL mod = 1e9 + 7;
const int N = 1e6 + 50;

struct SEG {
    int ls[N<<2], rs[N<<2], f[N<<2];
    void pushup(int rt) {
        f[rt] = min(f[rt<<1], f[rt<<1|1]);
    }
    void build(int rt, int l, int r) {
        ls[rt] = l, rs[rt] = r, f[rt] = INF;
        if(l == r) {
            return ;
        }
        int mid = (l + r) >> 1;
        build(rt << 1 , l, mid);
        build(rt << 1 | 1 , mid + 1, r);
    }
    void change(int rt, int p, int x) {
        if(ls[rt] == p && rs[rt] == p) {
            f[rt] = x;
            return ;
        }
        int mid = (ls[rt] + rs[rt]) >> 1;
        if(p <= mid) {
            change(rt << 1, p, x);
        } else {
            change(rt << 1 | 1, p, x);
        }
        pushup(rt);
    }
    int query(int rt, int l, int r) {
        if(ls[rt] >= l && rs[rt] <= r) {
            return f[rt];
        }
        int mid = (ls[rt] + rs[rt]) >> 1;
        int res = INF;
        if(l <= mid) {
            res = min(res, query(rt << 1, l, r));
        }   
        if(r > mid) {
            res = min(res, query(rt << 1 | 1, l, r));
        }
        return res;
    }
}seg;

vector<int>v[N];
int n, t;

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(n, t);
    for(ri i = 1; i <= n; ++i) {
        int l, r;
        read(l, r);
        v[r+1].pb(l+1);
    }
    seg.build(1, 1, t + 1);
    seg.change(1, 1, 0);
    //write(seg.query(1, 1, 5));
    for(ri i = 2; i <= t + 1; ++i) {
        int tmp = INF;
        for(auto x : v[i]) {
            //write(seg.query(1, x - 1, i)), LF;
            tmp = min(tmp, seg.query(1, x - 1, i) + 1);
        }
        seg.change(1, i, tmp);
    }
    int ans = seg.query(1, t + 1, t + 1);
    if(ans == INF) {
        write(-1);
    } else {
        write(ans);
    }
    LF;
    return 0;
}


活动打卡代码 AcWing 135. 最大子序和

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define pb push_back
#define mk make_pair
#define sz(x) (int)(x).size()
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL mod = 1e9 + 7;
const int N = 3e5 + 50;

LL n, m, t, s[N];
deque<int>q;

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(n, m);
    for(ri i = 1; i <= n; ++i) {
        read(t);
        s[i] = s[i-1] + t;
    }
    q.pb(0);
    LL ans = -INF;
    for(ri i = 1; i <= n; ++i) {
        while(!q.empty() && q.front() < i - m) {
            q.pop_front();
        }
        ans = max(s[i] - s[q.front()], ans);
        while(!q.empty() && s[i] <= s[q.back()]) {
            q.pop_back();
        }
        q.pb(i);
    }
    write(ans), LF;
    return 0;
}


活动打卡代码 AcWing 299. 裁剪序列

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define pb push_back
#define mk make_pair
#define sz(x) (int)(x).size()
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL mod = 1e9 + 7;
const int N = 1e5 + 50;

LL n, m, a[N], q[N*3],f[N], l, r, cur, sum;
multiset<LL>se;

LL cal(int x) {
    return f[q[x]] + a[q[x+1]];
}

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(n, m);
    for(ri i = 1; i <= n; ++i) {
        read(a[i]);
    }
    mem(f, INF);
    f[0] = 0;
    for(ri i = 1; i <= n; ++i) {
        while(l <= r && a[i] >= a[q[r]]) {
            if(l < r) {
                se.erase(se.find(cal(r - 1)));
            }
            --r;
        }
        q[++r] = i;
        if(l < r) {
            se.insert(cal(r - 1));
        }
        sum += a[i];
        while(sum > m) {
            sum -= a[cur++];
        }
        while(l <= r && q[l] < cur) {
            if(l < r) {
                se.erase(se.find(cal(l)));
            }
            ++l;
        }
        if(l <= r) {
            f[i] = f[cur-1] + a[q[l]];
        }
        if(l < r) {
            f[i] = min(f[i], *se.begin());
        }
    }
    /*for(ri i = 1; i <= n; ++i) {
        write(f[i]), SP;
    }
    LF;*/
    write(f[n]), LF;
    return 0;
}


活动打卡代码 AcWing 298. 围栏

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define pb push_back
#define mk make_pair
#define sz(x) (int)(x).size()
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL mod = 1e9 + 7;
const int N = 16050;

int f[110][N], n, m;

struct suc{
    int l, p, s;
}a[110];

bool operator < (suc a, suc b) {
    return a.s < b.s;
}

deque<int>q;

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(n, m);
    for(ri i = 1; i <= m; ++i) {
        read(a[i].l, a[i].p, a[i].s);
    }
    sort(a + 1, a + m + 1);
    for(ri i = 1; i <= m; ++i) {
        while(!q.empty()) {
            q.pop_front();
        }
        for(ri j = max(0, a[i].s - a[i].l); j <= a[i].s - 1; ++j) {
            while(!q.empty() && f[i-1][q.back()] - a[i].p * q.back() <= f[i-1][j] - a[i].p * j) {
                q.pop_back();
            }
            q.pb(j);
        }
        for(ri j = 1; j <= n; ++j) {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
            if(j >= a[i].s) {
                while(!q.empty() && q.front() < j - a[i].l) {
                    q.pop_front();
                }
                if(!q.empty()) {
                    f[i][j] = max(f[i-1][q.front()]  - a[i].p * q.front() + a[i].p * j, f[i][j]);
                }
            }
        }
    }
    write(f[m][n]), LF;
    return 0;
}



题目链接 AcWing298.围栏

这道题我设状态f[i]表示只对前i个木板进行粉刷的时候的最大报酬,转移方程为$f[i]=f[k-1]+(i-k+1)*p_x$。x是满足$s_x+l_x-1>=i>=s_x$的木匠。暴力转移交了一发,没成想过了。但看题解都是设置二维状态,用单调队列优化。我想问一下我这样写是没问题的还是数据比较弱。

代码:

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define pb push_back
#define mk make_pair
#define sz(x) (int)(x).size()
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL mod = 1e9 + 7;
const int N = 20000;

LL f[N], n, m;
struct suc {
    LL l, p, s;
}a[105];

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(n, m);
    for(ri i = 1; i <= m; ++i) {
        read(a[i].l, a[i].p, a[i].s);
    }
    for(ri i = 1; i <= n; ++i) {
        for(ri j = 1; j <= m; ++j) {
            if(i >= a[j].s && i <= a[j].s + a[j].l - 1) {
                for(ri k = max(i - a[j].l + 1, 1LL); k <= a[j].s - 1; ++k) {
                    f[i] = max(f[i], f[k-1] + (i - k + 1) * a[j].p);
                }
            }
        }
        f[i] = max(f[i], f[i-1]);
    }
    /*for(ri i = 1; i <= n; ++i) {
        write(f[i]), SP;
    }
    LF;*/
    write(f[n]), LF;
    return 0;
}


活动打卡代码 AcWing 332. 股票交易

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define pb push_back
#define mk make_pair
#define sz(x) (int)(x).size()
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL mod = 1e9 + 7;
const int N = 2e3 + 50;

int n, maxp, w, as[N], bs[N];
LL ap[N], bp[N], f[N][N];
deque<int>q;

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(n, maxp, w);
    for(ri i = 1; i <= n; ++i) {
        read(ap[i], bp[i], as[i], bs[i]);
    }
    mem(f, -INF);
    for(ri i = 1; i <= n; ++i) {
        for(ri j = 0; j <= as[i]; ++j) {
            f[i][j] = -j * ap[i];
        }
        for(ri j = 0; j <= maxp; ++j) {
            f[i][j] = max(f[i][j], f[i-1][j]);
        }
        if(i >= w + 1) {
            while(!q.empty()) {
                q.pop_front();
            }
            for(ri j = 0; j <= maxp; ++j) {
                while(!q.empty() && q.front() < j - as[i]) {
                    q.pop_front();
                }
                while(!q.empty() && f[i-w-1][q.back()] + 1LL * q.back() * ap[i] <= f[i-w-1][j] + 1LL * j * ap[i]) {
                    q.pop_back();
                }
                q.pb(j);
                f[i][j] = max(f[i][j], f[i-w-1][q.front()] + 1LL * q.front() * ap[i] - j * ap[i]);
            }
            while(!q.empty()) {
                q.pop_front();
            }
            for(ri j = maxp; j >= 0; --j) {
                while(!q.empty() && q.front() > j + bs[i]) {
                    q.pop_front();
                }
                while(!q.empty() && f[i-w-1][q.back()] + 1LL * q.back() * bp[i] <= f[i-w-1][j] + 1LL * j * bp[i]) {
                    q.pop_back();
                }
                q.pb(j);
                f[i][j] = max(f[i][j], f[i-w-1][q.front()] + 1LL * q.front() * bp[i] - j * bp[i]);
            }
        }
    }
    LL ans = -INF;
    for(ri i = 0; i <= maxp; ++i) {
        ans = max(ans, f[n][i]);
    }
    write(ans), LF;
    return 0;
}
/*
5 3 1
2 1 2 1
1 3 1 1
4 2 3 3
1 2 3 3
1 5 2 1

6 6 2
2 1 3 4
5 5 6 2
1 1 2 1
1 2 4 1
6 6 2 2
4 3 2 1
*/