制作购物网站,济南网站建设,不需要iis的网站开发,上海推牛网络科技有限公司比较套路的题目
首先肯定贪心一波#xff0c;两个都排序后尽量相连。我一开始猜最多跨1#xff0c;但其实最多跨2#xff0c;考虑3个人的情况#xff1a; 我们发现第3个人没了#xff0c;所以可以出现跨2的情况
然后直接上dp#xff0c;由 i − 1 , i − 2 , i − 3 i…比较套路的题目
首先肯定贪心一波两个都排序后尽量相连。我一开始猜最多跨1但其实最多跨2考虑3个人的情况 我们发现第3个人没了所以可以出现跨2的情况
然后直接上dp由 i − 1 , i − 2 , i − 3 i-1,i-2,i-3 i−1,i−2,i−3 转移过来。
然后这显然可以拿矩阵表示。
然后显然可以拿线段树维护。
后面三部分都是比较套路的。
#includebits/stdc.h
using namespace std;
#define int long long
inline int read(){int x0,f1;char chgetchar();
while(ch0||ch9){if(ch-)f-1;
chgetchar();}while(ch0ch9){x(x1)
(x3)(ch^48);chgetchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define M
//#define mo
#define N 30010
int n, m, i, j, k, T;
int a[N], b[N], ia[N], ib[N], shu[N], pos[N], x, y, q, rt; int Not(int x, int y) { if(shu[ia[x]]!ib[y]) return 1; return 0; }struct Martix {int c[3][3]; void mem() { memset(c, 0, sizeof(c)); }void init() { mem(); c[0][0]c[1][1]c[2][2]1; }void min() { c[0][0]c[0][1]c[0][2]c[1][0]c[1][1]c[1][2]c[2][1]c[2][2]c[2][0]-1e15; }Martix operator *(const Martix A) const { //maxMartix B; B.min(); for(int i0; i3; i) for(int j0; j3; j) for(int k0; k3; k) B.c[i][j]max(B.c[i][j], c[i][k]A.c[k][j]); return B; }void make(int x) {//生成在x位置的矩阵 min(); c[1][0]c[2][1]0; if(Not(x, x)) c[0][0]a[x]*b[x];
// if(x1) return printf(# 1 : \n), (*this).print(), void(); if(x1) return ; if(Not(x, x-1) Not(x-1, x)) c[0][1]a[x]*b[x-1]a[x-1]*b[x];
// if(x2) return printf(# 2: \n), (*this).print(), void(); if(x2) return ; if(Not(x, x-1) Not(x-1, x-2) Not(x-2, x)) c[0][2]max(c[0][2], a[x]*b[x-1]a[x-1]*b[x-2]a[x-2]*b[x]); if(Not(x, x-2) Not(x-1, x) Not(x-2, x-1)) c[0][2]max(c[0][2], a[x]*b[x-2]a[x-1]*b[x]a[x-2]*b[x-1]); if(Not(x, x-2) Not(x-1, x-1) Not(x-2, x)) c[0][2]max(c[0][2], a[x]*b[x-2]a[x-1]*b[x-1]a[x-2]*b[x]);
// printf(# %lld : \n, x); (*this).print(); }int que() {
// printf(RT : );
// (*this).print(); Martix B; B.min(); B.c[0][0]0; B(*this)*B; return B.c[0][0]; }void print() {printf(---\n); for(int i0; i3; i, printf(\n)) for(int j0; j3; j) printf(%lld , c[i][j]); printf(\n); }
};struct Segment_tree {int tot, ls[N2], rs[N2]; Martix s[N2]; void push_up(int k) { s[k]s[rs[k]]*s[ls[k]]; } //注意乘法顺序 void build(int k, int l, int r) {if(!k) ktot; if(lr) return s[k].make(l), void(); int mid(lr)1; build(ls[k], l, mid); build(rs[k], mid1, r); push_up(k); }void modify(int k, int l, int r, int x) {if(lr) return s[k].make(x), void(); int mid(lr)1; if(xmid) modify(ls[k], l, mid, x); else modify(rs[k], mid1, r, x); push_up(k);
// printf([%lld %lld] : \n, l, r); s[k].print(); }
}Seg;signed main()
{
// freopen(in.txt, r, stdin);
// freopen(out.txt, w, stdout);
// srand(time(NULL));
// Tread();
// while(T--) {
//
// }nread(); qread(); for(i1; in; i) a[i]read(), ia[i]i, shu[i]i; //shu第i个人马的编号 for(i1; in; i) b[i]read(), ib[i]i; sort(ia1, ian1, [] (int x, int y) { return a[x]a[y]; }); sort(ib1, ibn1, [] (int x, int y) { return b[x]b[y]; }); sort(a1, an1); reverse(a1, an1); //按实力排好则原顺序已经没必要了 sort(b1, bn1); reverse(b1, bn1);
// coutia : ; for(i1; in; i) printf(%lld , ia[i]); puts();
// coutib : ; for(i1; in; i) printf(%lld , ib[i]); puts();
// couta : ; for(i1; in; i) printf(%lld , a[i]); puts();
// coutb : ; for(i1; in; i) printf(%lld , b[i]); puts(); //ia, ib排序后排名第i对应的原编号 for(i1; in; i) pos[ia[i]]i; //某编号对应的排名
// coutpos : ; for(i1; in; i) printf(%lld , pos[i]); puts(); Seg.build(rt, 1, n); while(q--) {xread(); yread(); swap(shu[x], shu[y]); //交换了马
// coutshu : ; for(i1; in; i) printf(%lld , shu[i]); puts(); for(imax(1ll, pos[x]-3); imin(n, pos[x]3); i) Seg.modify(1, 1, n, i); for(imax(1ll, pos[y]-3); imin(n, pos[y]3); i) Seg.modify(1, 1, n, i); printf(%lld\n, Seg.s[1].que()); }return 0;
}
