「NOIP Record」#10 单调性优化与双指针
|
Record
|

2967 字
|
34 分钟

luogu8551 Bassline

题目的限制翻译过来就是 $[x,y]$ 中任意位置都被覆盖了相同次数。

用差分求出每个点被覆盖的次数，双指针求极长的满足条件的位置即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=3e5+5;
int n, ans, c[N], isl[N];
signed main() {
    n=read();
    int L=1e15, R=0;
    rep(i,1,n) {
        int l=read(), r=read();
        L=min(L,l), R=max(R,r);
        ++c[l], --c[r+1];
        isl[l]=1;
    }
    rep(i,L,R) c[i]+=c[i-1];
    int l=L, r=L;
    while(r<=R) {
        while(r<R&&c[r+1]==c[r]&&!isl[r+1]) ++r;
        ans=max(ans,c[l]*(r-l));
        l=r=r+1;
    }
    printf("%lld\n",ans);
}

luogu8587 新的家乡

注意到值域不大，直接枚举柱子的高度，然后在值域上双指针匹配即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=1e6+5, M=6e3+5;
int n, mx, mn=1e5, cnt, h[N], c[M];
bool v[N];
int hh[M], d[M];
int solve(int x) {
    int l=mn-1, r=x-mn, res=0;
    while(l<=r) {
        ++l;
        while(l<=r&&!c[l]) ++l;
        while(l<=r&&!c[r]) --r;
        while(l<=r&&l+r>x) --r;
        if(l<=r&&c[l]&&c[r]&&l+r==x) {
            if(l<r) res+=min(c[l],c[r]);
            else if(l==r) res+=c[l]/2;
        }
    }
    return res;
}
signed main() {
    n=read();
    rep(i,1,n) h[i]=read(), ++c[h[i]], mx=max(mx,h[i]), mn=min(mn,h[i]);
    rep(i,1,mx) if(c[i]) {
        rep(j,1,mx) if(c[j]) {
            if(!v[i+j]) v[i+j]=1, hh[++cnt]=i+j;
        }
    }
    int res=0, ans=0;
    rep(i,1,cnt) {
        d[i]=solve(hh[i]);
        res=max(res,d[i]);
    }
    rep(i,1,cnt) if(d[i]==res) ++ans;
    printf("%lld %lld\n",res,ans);
}

luogu8590 『JROI-8』这是新历的朝阳，也是旧历的残阳

最优方案一定是让负数尽可能小，正数尽可能大。因此所有正数必然都被划分进最后一个段，而负数则要在最后一段与第一段中取最大值。

设最后一个负数的位置是 $p$，不难想到一定存在一个这样的临界位置 $p$，使得 $[1,p-1]$ 在第 $1$ 段（序列单调不降），$[p,n]$ 在最后一段。设当前分 $m$ 段，那就是 $i$ 是满足 $(a_p+1)^2 \le (a_p+m)^2$ 的第一个元素，并且随着 $m$ 的增长，$p$ 单调不增。

考虑如何快速统计答案。设划分了 $m$ 段，那么答案就是$$\sum_{i=1}^{p-1} (a_i+1)^2 + \sum_{i=p}^n (a_i+m)^2$$

$$
\sum_{i=1}^{p-1} (a_i^2 + 2a_i+1) + \sum_{i=p}^n (a_i^2 + 2ma_i + m^2)
$$

$$
\sum_{i=1}^n a_i^2 + 2 \sum_{i=1}^{p-1} a_i + 2m \sum_{i=p}^n a_i + (n-p+1) \times m + p-1
$$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=1e6+5, M=1e7+5, mod=998244353;
int n, k, a[N], s[N], s2[N];
int squ(int x) { return x*x; }
int bs(int x) {
    int l=1, r=n;
    while(l<r) {
        int mid=(l+r)>>1;
        if(squ(a[mid]+1)<squ(a[mid]+x)) r=mid; else l=mid+1;
    }
    return l!=n? l:n+1;
}
signed main() {
    n=read(), k=read();
    int ans=0;
    rep(i,1,n) {
        a[i]=read();
        s[i]=(s[i-1]+a[i])%mod, s2[i]=(s2[i-1]+a[i]*a[i])%mod;
        (ans+=(a[i]+1)*(a[i]+1)%mod)%=mod;
    }
    int l=n+1;

    rep(x,2,k) {
        while(l>1&&squ(a[l-1]+1)<=squ(a[l-1]+x)) --l;
        (ans+=(s2[l-1]+2*s[l-1]%mod+(l-1))%mod)%=mod;
        (ans+=(s2[n]-s2[l-1]+mod)%mod)%=mod;
        (ans+=2*(s[n]-s[l-1]+mod)%mod*x%mod)%=mod;
        (ans+=(n-l+1)*x%mod*x%mod)%=mod;
    }
    printf("%lld\n",ans);
}

luogu8858 折线

手玩几下，发现答案只能是 $2,3,4$ 其中之一。

答案是 $2$ 的充要条件是把所有点按照 $x$ 或 $y$ 排序后，第 $\frac{n}{2}$ 和第 $\frac{n}{2}+1$ 个点对应的坐标不同。

而答案是 $4$ 的情况不太好直接刻画，考虑从答案为 $3$ 下手。

不难发现如果答案是 $3$，那么一定存在一个这样的结构





如何求这个东西？

它最大的特征就是形成了一个横坐标或纵坐标反着的二维偏序。

对于第一张图的情况，考虑横坐标递减的过程，维护一个纵坐标 $j$，表示能使这条折线下面的点数不小于 $\frac{n}{2}$ 的折点纵坐标，这玩意也是单调减的。如果在递减的过程中找到了使得下面的点数为 $\frac{n}{2}$ 的折点，那么答案就是 $3$。

对于第二张图的情况，按纵坐标递减，维护横坐标即可。

需要离散化，然后用树状数组维护点数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=5e5+5;
int T, n, m, ans, t[2*N];
struct node {
    int x, y;
} a[N];
bool cmp1(node a,node b) {
    return a.x==b.x? a.y<b.y:a.x<b.x;
    // 按照横坐标排序
}
bool cmp2(node a,node b) {
    return a.y==b.y? a.x<b.x:a.y<b.y;
    // 按照纵坐标排序
}
void lsh() {
    sort(t+1,t+m+1);
    m=unique(t+1,t+m+1)-t-1;
    rep(i,1,n) {
        a[i].x=lower_bound(t+1,t+m+1,a[i].x)-t;
        a[i].y=lower_bound(t+1,t+m+1,a[i].y)-t;
    }
}
struct BIT {
    int c[N];
    void modify(int x,int y) {
        for(;x<=n;x+=x&-x) c[x]+=y;
    }
    int query(int x) {
        int y=0;
        for(;x;x-=x&-x) y+=c[x];
        return y;
    }
} Tr;
void solve() {
    n=read();
    ans=4, m=0;
    rep(i,1,n) {
        a[i].x=t[++m]=read();
        a[i].y=t[++m]=read();
    }
    lsh();
    sort(a+1,a+n+1,cmp1);
    int i=n, j=n+1;
    if(a[n/2].x!=a[n/2+1].x) { ans=min(ans,2ll); goto out; }
    while(i>0) {
        while(a[i].x==a[i-1].x) Tr.modify(a[i].y,1), --i;
        // 坐标相同的点就直接插进去
        Tr.modify(a[i].y,1), --i;
        for(;j>1&&Tr.query(j-1)>=n/2;) --j;
        while(j>1&&Tr.query(j-1)>=n/2) --j;
        if(Tr.query(j)==n/2) ans=min(ans,3ll);
    }
    rep(i,1,n) Tr.modify(a[i].y,-1);
    sort(a+1,a+n+1,cmp2);
    if(a[n/2].y!=a[n/2+1].y) { ans=min(ans,2ll); goto out; }
    i=n, j=n+1;
    while(i>0) {
        while(a[i].y==a[i-1].y) Tr.modify(a[i].x,1), --i;
        Tr.modify(a[i].x,1), --i;
        for(;j>1&&Tr.query(j-1)>=n/2;) --j;
        if(Tr.query(j)==n/2) ans=min(ans,3ll);
    }
    rep(i,1,n) Tr.modify(a[i].x,-1);
    out: printf("%lld\n",ans);
}
signed main() {
    T=read();
    while(T--) solve();
}

luogu7514 [省选联考 2021 A/B 卷] 卡牌游戏

把正反卡牌都放到一起排序，那么一种方案的极差就是一个区间的左右端点之差。一个区间 $[l,r]$ 是合法的，意味着区间内不存在相同的卡牌编号，以及出现反面不超过 $m$ 次，等价于 $[1,l-1]$ 与 $[r+1,n]$ 不出现相同的卡牌编号，并且出现正面不超过 $m$ 次。

考虑右端点递增的过程，不难发现对应的 $l$ 单调不降。因此只需要在一个初始区间上双指针维护即可。

如何找这个初始区间呢？我们考虑的是 $r$ 递增的过程，所以只要在最小化 $r$ 的基础上，找到最大的 $l$ 即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=1e6+5;
int n, m, ans=1e15;
bool v[N];
struct cd {
    int x, id, st;
} a[2*N];
bool operator<(cd a,cd b) {
    return a.x<b.x;
}
signed main() {
    n=read(), m=read();
    rep(i,1,n) a[i].x=read(), a[i].id=i, a[i].st=1;
    rep(i,1,n) a[i+n].x=read(), a[i+n].id=i, a[i+n].st=0;
    sort(a+1,a+2*n+1);
    int l=1, r=2*n, cnt=0;
    while(cnt+a[r].st<=m&&!v[a[r].id]) v[a[r].id]=1, cnt+=a[r].st, --r;
    while(cnt+a[l].st<=m&&!v[a[l].id]) v[a[l].id]=1, cnt+=a[l].st, ++l;
    ans=min(ans,a[r].x-a[l].x);
    while(r<2*n) {
        v[a[r+1].id]=0, cnt-=a[r+1].st, ++r;
        while(cnt+a[l].st<=m&&!v[a[l].id]) v[a[l].id]=1, cnt+=a[l].st, ++l;
        ans=min(ans,a[r].x-a[l].x);
    }
    printf("%lld\n",ans);
}

luogu4805 [CCC2016] 合并饭团

先转化一下题意。虽然不像石子合并一样需要把所有饭团合并成一个，但是直接当要求合并成一个来做就行，因为任何饭团都是由一个区间内所有饭团合并而来的。

设 $f(i,j)$ 表示 $[i,j]$ 能合并成一个多大的饭团，那么只有第一种合并方式的情况就做完了。仔细想想合并满足结合律，如果一个区间能合并成一个，那么所有合并方式得到的结果都相同。

考虑第二种操作。一种直接做的方法是，对于每个 $f(k,j)$，把它扔进值域桶里面，并记录对应的 $k$。然后枚举 $f(i,k’)$，找到桶里 $f(i,k’)$ 这个值对应的 $k$，并判断 $f(k’+1,k-1)$ 能否合并成一个，最后取最大值即可。这样做需要用到std::unordered_map，效率较低。

考虑直接维护中间那个饭团对应的区间 $[l,r]$，由于长度更大的区间能合并成的饭团更大，所以是有单调性的，用双指针匹配即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=405;
int n, ans, f[N][N];
signed main() {
    n=read();
    rep(i,1,n) f[i][i]=read(), ans=max(ans,f[i][i]);
    for(int l=2;l<=n;++l) for(int i=1;i+l-1<=n;++i) {
        int j=i+l-1;
        for(int k=i;k<j;++k) if(f[i][k]&&f[k+1][j]&&f[i][k]==f[k+1][j]) {
            f[i][j]=f[i][k]+f[k+1][j];
            break;
        }
        int L=i, R=j;
        while(L<=R-2) {
            while(L<=R-2&&!f[i][L]) ++L;
            while(L<=R-2&&!f[R][j]) --R;
            if(f[i][L]<f[R][j]) ++L;
            else if(f[i][L]>f[R][j]) --R;
            else if(!f[L+1][R-1]) ++L, --R;
            if(L<=R-2&&f[i][L]&&f[L+1][R-1]&&f[R][j]&&f[i][L]==f[R][j]) {
                f[i][j]=max(f[i][j],f[i][L]+f[L+1][R-1]+f[R][j]);
                break;
            }
        }
        ans=max(ans,f[i][j]);
    }
    printf("%lld\n",ans);
}

luogu3724 [AHOI2017/HNOI2017] 大佬

Solution

题意很复杂，我们要从中提取关键信息。

增加等级、嘲讽能力都是为了怼大佬服务，而怼大佬最多使用 $2$ 次，我们尝试把这个操作单独拿出来，这样要考虑的就只剩下了还嘴和做水题。

考虑这样一个东西：由于我们保证自己不死，所以除了做水题回血之外，剩下的时间都可以空出来，在我们需要的时候手动添加具体操作。

设 $f_{i,j}$ 为考虑前 $i$ 天，空出来了 $j$ 天，所剩下的最大体力。$$f_{i,j} = \max\begin{cases}\min(f_{i-1,j} – a_i + w_i,mc) & f_{i-1,j} \ge a_i\f_{i-1,j-1} – a_i & f_{i-1,j-1} \ge a_i\end{cases}$$ 然后取 $maxd$ 为所有满足 $f_{i,j} \ge 0$ 的最大的 $j$，表示能空出的最大天数。

注意不一定要取 $f_{n,j}$，因为如果在第 $n$ 天之前把大佬干掉并且自己存活，那么也算胜利。因此如果 $maxd$ 不在 $f_{n,j}$ 处取得并且能在 $maxd$ 天之内干掉大佬，那么无妨；如果干不死，那么取 $f_{n,j}$ 处的也干不掉。

如果 $C \le maxd$，那么每天还嘴就行，否则就需要在 $maxd$ 天之内安排一次或两次怼大佬，但是怼大佬也不一定总是比还嘴优，不太好处理。

但是 $maxd$ 并不大，考虑把所有合法的怼大佬方法都搜索出来。设 $(d,F,L)$ 为用时 $d$ 天，能力为 $F$，等级为 $L$ 的状态。

如果是怼一次大佬，那么直接枚举所有状态，找到 $F+maxd-d \ge C$ 的状态即可。

如果一次不够，那么我们就找两个满足 $F_1+F_2+maxd-d_1-d_2 \ge C$ 的状态。注意到式子的值与 $F$ 正相关，与 $d$ 负相关，那就按照 $F$ 递增为第一关键字，$d$ 递减为第二关键字排序。这样对于一个 $(d_1,F_1,L_1)$，其最优决策就是满足 $F_1+F_2 \le C$ 的编号最大的 $(d_2,F_2,L_2)$，同时 $F_1$ 具有单调性，决策也就单调了，用双指针做就行。

最后是如何搜索的问题。虽然状态有三维，直观上数量不在少数，但是只有 $(F,L)$ 才有用，$d$ 这一维是要用最优化的。$d$ 每次只会增长 $1$，用 $\text{BFS}$ 即可。记录状态可以用std::map<pair<int,int>,bool>，但效率不高。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=105;
int n, m, mc, maxd, a[N], w[N];
int f[N][N];
struct node {
    int d, L, F;
    node() {};
    node(int _d,int _L,int _F) { d=_d, L=_L, F=_F; };
};
bool operator<(node a,node b) {
    if(a.F!=b.F) return a.F<b.F;
    if(a.d!=b.d) return a.d>b.d;
    return a.L<b.L;
}
vector<node> st;
map<PII,bool> p;
void bfs() {
    queue<node> q;
    q.push(node(1,0,1)), st.pb(node(1,0,1));
    // 初始d设置为1，把怼大佬那一天提前算了
    p[MP(0,1)]=1;
    // pair要存(L,F)，否则TLE
    while(q.size()) {
        node x=q.front(), s; q.pop();
        if(x.d>=maxd) continue;
        PII t=MP(x.L+1,x.F);
        if(p[t]) continue;
        if(x.d<maxd) {
            p[t]=1;
            s=node(x.d+1,x.L+1,x.F);
            q.push(s), st.pb(s);
        }
        t=MP(x.L,x.F*x.L);
        if(t.fi<=1||t.se>1e8||p[t]) continue;
        p[t]=1;
        s=node(x.d+1,x.L,x.F*x.L);
        q.push(s), st.pb(s);
    }
    sort(st.begin(),st.end());
}
signed main() {
    n=read(), m=read(), mc=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,n) w[i]=read();
    SET(f,-1);
    f[0][0]=mc;
    rep(i,1,n) rep(j,0,i) {
        if(f[i-1][j]>=a[i]) f[i][j]=max(f[i][j],min(f[i-1][j]-a[i]+w[i],mc));
        if(j&&f[i-1][j-1]>=a[i]) f[i][j]=max(f[i][j],f[i-1][j-1]-a[i]);
    }
    rep(i,1,n) rep(j,1,i) if(f[i][j]>=0) maxd=max(maxd,j);
    bfs();
    while(m--) {
        int C=read();
        if(C<=maxd) { puts("1"); continue; }
        int l=0, r=st.size()-1;
        for(int i=0;i<st.size();++i) {
            if(st[i].F<=C&&st[i].F+maxd-st[i].d>=C) { puts("1"); goto qwq; }
        }
        for(;l<=r;++l) {
            while(l<=r&&st[l].F+st[r].F>C) --r;
            if(l<=r&&st[l].F+st[r].F+maxd-st[l].d-st[r].d>=C) { puts("1"); goto qwq; }
        }
        puts("0");
        qwq:;
    }
}

luogu6563 [SBCOI2020] 一直在你身旁

不妨称需要的电线为答案电线。

注意到购买长度为 $k$ 的电线本质上是把答案电线的取值范围从 $[i,j]$ 缩小到了 $[i,k]$ 或 $[k+1,j]$。虽然无法确定到底是在哪一个区间，但是最坏的情况一定是答案电线在二者中代价更大的里面，同时我们完成了对子问题的划分，直接上区间 DP。

我们把拓扑序反过来，使得这个过程符合区间 DP。设 $f(i,j)$ 为答案电线的取值范围是 $[i,j]$ 时，最坏情况下找到答案电线还需要的最小代价。

显然有

$$
f(i,j) = \min_{k \in [i,j-1]} \Big\{ \max \{(f(i,k),f(k+1,j) \} + a_k \Big\}
$$

考虑优化。

打表发现确实有决策单调性，但是是分段单调，不太容易下手。

从实际意义的角度似乎不是很显然。

套路地把 $\max$ 拆开，考虑会在哪边取到。

注意到 ${a_i}$ 单调不降，再感性理解一下，$f(i,k)$ 关于 $k$ 单调增，$f(k+1,j)$ 关于 $k+1$ 单调减，从而 $f(i,k)-f(k+1,j)$ 关于 $k$ 单调不降，也就是存在临界点。

可以用二分找到最小的使得 $f(i,k)>f(k+1,j)$ 的 $k$，记为 $p$。

然而有 $f(i,j) \le f(i,j+1)$，所以在 $i$ 或者 $j$ 变化时，$p$ 也是单调的，用一个指针维护即可。

接下来讨论一个决策点 $k$ 与 $p$ 的关系。

  • $k < p$。此时取到的是 $f(k+1,j)+a_k$，发现这东西和 $i$ 无关。在 $j$ 固定时可以用单调队列维护。
  • $k \ge p$，此时取到的时 $f(i,k)+a_k$，它关于 $k$ 单调增，最终取到的一定是 $f(i,p)+a_p$。

综上所述，在右端点固定，左端点递减时，我们可以做到均摊 $O(1)$ 地转移。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=7105;
int T, n, a[N];
int q[N];
ll f[N][N];
void solve() {
    n=read();
    rep(i,1,n) a[i]=read();
    for(int j=2;j<=n;++j) {
        int l=1, r=0;
        f[j-1][j]=a[j-1];
        q[++r]=j-1;
        for(int i=j-2,k=j;i;--i) {
            while(k>i&&f[i][k-1]>f[k][j]) --k;
            while(l<=r&&q[l]>=k) ++l;
            f[i][j]=f[i][k]+a[k];
            if(l<=r) f[i][j]=min(f[i][j],f[q[l]+1][j]+a[q[l]]);
            while(l<=r&&f[q[r]+1][j]+a[q[r]]>=f[i+1][j]+a[i]) --r;
            q[++r]=i;
        }
    }
    printf("%lld\n",f[1][n]);
}
signed main() {    T=read();
    while(T--) solve();
    return 0;
}
区间DP双指针树状数组
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇