企业网站制作要求,代运营公司介绍,多渠道营销系统,网站突然不收录了感谢grass8sheep提供的思路。
首先#xff0c;我们可以用 D P DP DP解决这个问题。
设 f i , j f_{i,j} fi,j表示前 i i i个数中有 j j j个为 1 1 1的位置为红色的最大价值。则转移如下#xff1a; f i , j ← f i − 1 , j b i f_{i,j}\gets f_{i-1,j}b_i fi,j←fi−…感谢grass8sheep提供的思路。
首先我们可以用 D P DP DP解决这个问题。
设 f i , j f_{i,j} fi,j表示前 i i i个数中有 j j j个为 1 1 1的位置为红色的最大价值。则转移如下 f i , j ← f i − 1 , j b i f_{i,j}\gets f_{i-1,j}b_i fi,j←fi−1,jbi若 s i 1 s_i1 si1有转移 f i , j ← f i − 1 , j − 1 r i f_{i,j}\gets f_{i-1,j-1}r_i fi,j←fi−1,j−1ri若 s i 0 s_i0 si0有转移 f i , j ← f i − 1 , j − j r i f_{i,j}\gets f_{i-1,j}-jr_i fi,j←fi−1,j−jri
初始 f 0 , j 0 f_{0,j}0 f0,j0。
考虑差分序列记作 { d i } \{d_i\} {di}。则 s i 1 s_i1 si1的转移等价于对于一段连续的满足 r i − b i r_i-b_i ri−bi的区间将 d i d_i di向后依次挪动一位然后在开头插入 r i − b i r_i-b_i ri−bi记为操作一。 s i 2 s_i2 si2则等价于对于 [ 1 , r i − b i ] [1,r_i-b_i] [1,ri−bi]这段前缀的 d i d_i di减去 1 1 1记为操作二。注意如果 r i − b i 0 r_i-b_i0 ri−bi0那么一定是贪心的选择 b i b_i bi。
但是打表可以发现答案不是凸的也就是说 d i d_i di不具有单调性。事实上有一个结论每次结束后将 d i d_i di按从大到小排序这并不会影响答案。因此用平衡树维护即可操作一对应区间平移操作二对应前缀减 1 1 1然后将差值为一的两个连续段交换。
复杂度 O ( n log n ) O(n\log n) O(nlogn)。
关于结论的证明设 d p j dp_j dpj表示考虑完前 i i i个数后选了 j j j个 1 1 1的最大价值 d p j a dp_{j}a dpja d p j 1 a b dp_{j1}ab dpj1ab d p j 2 a 2 b 1 dp_{j2}a2b1 dpj2a2b1。设之后的方案中选了 x x x个 0 0 0那么我们要让 d p i − i x dp_i-ix dpi−ix最大。发现交换了 d j 1 d_{j1} dj1和 d j 2 d_{j2} dj2后 j 1 j1 j1仍然不可能成为答案。考虑是一条直线来截每个点使得截矩最大因为斜率是整数而相邻两点间斜率之差又不超过 1 1 1因此不可能截到中间那个点
因为每次操作是前缀减 1 1 1所以交换的两个段之差不会超过 1 1 1因此结论是正确的。 remark \text{remark} remark 注意到 D P DP DP只要不漏就好了因此在不影响正确性的情况下我们可以修正 D P DP DP值。
类似的 D P DP DP思路[USACO21DEC] Paired Up P做法不一样但是都有对 D P DP DP最优性的一些思考
#includebits/stdc.h
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
using namespace std;
const int N4e55;
int T,n,tot,rt;
ll r[N],b[N];
string str;
mt19937 gen(time(0));
struct node{int fix,l,r,sz;ll tag,val;
}t[N];
void pushup(int p){t[p].szt[t[p].l].szt[t[p].r].sz1;
}
int newnode(ll val){tot;t[tot].fixgen(),t[tot].lt[tot].rt[tot].tag0,t[tot].sz1,t[tot].valval;return tot;
}
void add(int p,ll x){if(!p)return;t[p].valx,t[p].tagx;
}
void pushdown(int p){if(t[p].tag)add(t[p].l,t[p].tag),add(t[p].r,t[p].tag),t[p].tag0;
}
int merge(int x,int y){if(!x||!y)return xy;if(t[x].fixt[y].fix){pushdown(x);t[x].rmerge(t[x].r,y);pushup(x);return x;}else{pushdown(y);t[y].lmerge(x,t[y].l);pushup(y);return y;}
}
void split0(int rt,int x,int y,ll val){if(!rt){xy0;return;}pushdown(rt);if(t[rt].valval){xrt;split0(t[x].r,t[x].r,y,val);pushup(x);}else{yrt;split0(t[y].l,x,t[y].l,val);pushup(y);}
}
void split1(int rt,int x,int y,int val){if(!rt){xy0;return;}pushdown(rt);if(t[t[rt].l].sz1val){xrt;split1(t[x].r,t[x].r,y,val-t[t[rt].l].sz-1);pushup(x);}else{yrt;split1(t[y].l,x,t[y].l,val);pushup(y);}
}
int rs(int x){while(t[x].r)xt[x].r;return x;
}
int ls(int x){while(t[x].l)xt[x].l;return x;
}
int cnt;
ll c[N];
void dfs(int x){pushdown(x);if(t[x].l)dfs(t[x].l);c[cnt]t[x].val;if(t[x].r)dfs(t[x].r);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinT;while(T--){cinnstr;for(int i1;in;i)cinr[i];for(int i1;in;i)cinb[i];rttot0;ll sm0;int c10;for(int i1;in;i){if(r[i]b[i]){smb[i];continue;}else if(str[i-1]1){c1,smb[i];int x,y;split0(rt,x,y,r[i]-b[i]);rtmerge(x,merge(newnode(r[i]-b[i]),y));}else{smr[i];int x,y;split1(rt,x,y,min(1ll*c1,r[i]-b[i]));if(!x||!y){add(x,-1);rtxy;}else{int _xrs(x),_yls(y);if(t[_x].valt[_y].val){ll valt[_x].val;int a,b,c,d;split0(x,a,b,val1);split0(y,c,d,val);add(a,-1),add(b,-1);rtmerge(merge(a,c),merge(b,d));}else{add(x,-1);rtmerge(x,y);}}}}cnt0,dfs(rt);ll ressm;for(int i1;ic1;i){smc[i],resmax(res,sm);}coutres\n;}
}
