menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[DP+线段树维护矩阵转移]Codeforces573D【Bear and Cavalry】题解
apps Codeforces
local_offer 查看标签
comment 2 条评论
remove_red_eye 590 次访问

题目概述

给出 $\{a_n\}$ 和 $\{b_n\}$ 以及刚开始 $P_i=i$ 的排列 $\{P_n\}$ ,有 $m$ 个询问,每次询问先交换 $P_x,P_y$ ,然后询问 $max\{\sum_{i=1}^{n}a_ib_{p_i}|p_i\not=P_i\}$ 。

解题报告

首先根据排序不等式(WTF这是啥?)可以证明 $\{a_n\}$ 和 $\{b_n\}$ 排序之后一一匹配答案最大,而且可以证明如果强制不能选那么交换相邻的来使得满足条件是最优秀的。感觉挺对的反正我不会证明。

但这一看就不可做吧……找结论开始:每个 $i$ 至多只会和距离为 $2$ 的点匹配。感觉挺对的反正我不会证明。

那么也就是说我们只需要考虑最多三个之间的连边情况,可以考虑DP:$f[i]$ 表示前 $i$ 个的最优解,从 $f[i-1],f[i-2],f[i-3]$ 转移。但是多组询问,这样是 $O(nm)$ 的,还是会炸。


学习新姿势!其实这种极值DP也可以用矩阵来转移,那么我们可以改变定义便于构造矩阵:$f[i][0/1/2]$ 表示 $1\sim i-0/1/2$ 已经匹配完成的最优解,那么可以构造这么一个矩阵:

$$ \begin{bmatrix} a_ib_i&0&-\infty\\ a_ib_{i-1}+a_{i-1}b_i &-\infty&0\\ max\{a_ib_{i-1}+a_{i-1}b_{i-2}+a_{i-2}b_i,a_ib_{i-2}+a_{i-1}b_i+a_{i-2}b_{i-1}\}&-\infty&-\infty \end{bmatrix} $$

当然矩阵中的式子需要满足 $p_i\not=P_i$ ,否则为 $-\infty$ 。而 $\{P_i\}$ 是会变动的,但我们知道变动波及的范围只有 $3$ 而已,而矩阵满足结合率,所以直接用线段树暴力维护就行了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define fr first
#define sc second
typedef long long LL;
const int maxn=30000;

int n,te,P[maxn+5],pos[maxn+5];pair<int,int> a[maxn+5],b[maxn+5];
#define dif(x,y) (P[a[x].sc]!=b[y].sc)
#define val(x,y) ((LL)a[x].fr*b[y].fr)
struct Matrix{
    LL s[3][3];void Clear() {memset(s,192,sizeof(s));}
    inline void Update(int x){
        Clear();s[0][1]=s[1][2]=0;if (dif(x,x)) s[0][0]=val(x,x);
        if (x>1) if (dif(x,x-1)&&dif(x-1,x)) s[1][0]=val(x,x-1)+val(x-1,x);
        if (x>2){
            if (dif(x,x-2)&&dif(x-1,x)&&dif(x-2,x-1)) s[2][0]=val(x,x-2)+val(x-1,x)+val(x-2,x-1);
            if (dif(x,x-1)&&dif(x-1,x-2)&&dif(x-2,x)) s[2][0]=max(s[2][0],val(x,x-1)+val(x-1,x-2)+val(x-2,x));
        }
    }
    inline LL MAX() {LL MAX=0;for (int i=0;i<3;i++) MAX=max(MAX,s[i][0]);return MAX;}
}mat[(maxn<<2)+5];

inline Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.Clear();
    for (int i=0;i<3;i++)
        for (int j=0;j<3;j++)
            for (int k=0;k<3;k++)
                c.s[i][j]=max(c.s[i][j],a.s[i][k]+b.s[k][j]);return c;
}
#define Pushup(p) (mat[p]=mat[p<<1]*mat[p<<1|1])
void Update(int pos,int l=1,int r=n,int p=1){
    if (l==r) return mat[p].Update(pos);int mid=l+(r-l>>1);
    if (pos<=mid) Update(pos,l,mid,p<<1); else Update(pos,mid+1,r,p<<1|1);Pushup(p);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&te);for (int i=1;i<=n;i++) P[i]=i;
    for (int i=1;i<=n;i++) scanf("%d",&a[a[i].sc=i].fr);sort(a+1,a+1+n);
    for (int i=1;i<=n;i++) scanf("%d",&b[b[i].sc=i].fr);sort(b+1,b+1+n);
    for (int i=1;i<=n;i++) pos[a[i].sc]=i,Update(i);
    for (int x,y;te;te--){
        scanf("%d%d",&x,&y);swap(P[x],P[y]);
        for (int i=pos[x];i<pos[x]+3&&i<=n;i++) Update(i);
        for (int i=pos[y];i<pos[y]+3&&i<=n;i++) Update(i);
        printf("%lld\n",mat[1].MAX());
    }
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
    Sdywolf Sdywolf
    Sdywolf
    2018-08-23 19:37:59Sdywolf
    keyboard_arrow_down
    2018-08-23 19:37:59

    那个好像是叫排序不等式啊?

    remove_red_eye
    访客
      2018-08-23 21:06:12ZigZagK
      keyboard_arrow_down
      2018-08-23 21:06:12

      哦……是吗QAQ,我太菜了

      account_circle
      博主
keyboard_arrow_up