danihao123's Blog

很不错的题啊……

很容易想到构造三维的状态，但无论时间还是空间都不好。我们可以构造[tex]f[i][delta][/tex]这种状态，表示用前[tex]i[/tex]块水晶，搭建出的双塔高度差为[tex]delta[/tex]时较大塔的高度。显然答案为[tex]f[n][0][/tex]。

转移的时候，要考虑放到高塔上还是低塔上，以及是否会导致高低塔地位对调。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=101,maxV=2001;
int d[2][maxV];
int V[maxn];
int main(){
	int n,maxj=0;
	register int i,j,now,pre;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&V[i]);
		maxj+=V[i];
	}
	memset(d,-1,sizeof(d));
	d[0][0]=0;
	for(i=1;i<=n;i++){
		now=i%2;
		pre=1-now;
		for(j=0;j<=maxj;j++){
			if(d[pre][j]>=0)
				d[now][j]=d[pre][j];
			if(V[i]<=j){
				if(d[pre][j-V[i]]>=0){
					d[now][j]=max(d[now][j],d[pre][j-V[i]]+V[i]);
				}
			}
			if(V[i]>j && d[pre][V[i]-j]>=0){
				d[now][j]=max(d[now][j],d[pre][V[i]-j]+j);
			}
			if(j+V[i]<=maxj && d[pre][j+V[i]]>=0)
				d[now][j]=max(d[now][j],d[pre][j+V[i]]);
		}
	}
	if(d[1&n][0]<=0)
		puts("Impossible");
	else
		printf("%d\n",d[1&n][0]);
	return 0;
}

这题是很经典的线段树题。

我们可以发现最长子序列或跨越中点，或不跨越中点。若不跨越则肯定在左子或右子中，跨越则是左子最大后缀和和右子最大前缀和之和。问题便迎刃而解。（当然，求区间最大前缀/后缀和要用上区间和）

需注意此题可能会出现a>b！

代码：

/**************************************************************
    Problem: 1756
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2604 ms
    Memory:49648 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500001;
struct Node{
    int L,R;
    int maxP,maxS,ans,sum;
};
Node Tree[maxn*4];
int A[maxn];
void merge(Node& O,Node& LC,Node& RC){
    O.sum=LC.sum+RC.sum;
    O.maxP=max(LC.maxP,LC.sum+RC.maxP);
    O.maxS=max(RC.maxS,RC.sum+LC.maxS);
    O.ans=max(max(LC.ans,RC.ans),LC.maxS+RC.maxP);
}
void maintain(int o){
    Node& O=Tree[o],LC=Tree[o<<1],RC=Tree[o<<1|1];
    merge(O,LC,RC);
}
void build_tree(int o,int L,int R){
    Node& O=Tree[o];
    O.L=L;
    O.R=R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=A[L];
    }else{
        int M=L+(R-L)/2;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
        maintain(o);
    }
}
void update(int o,int p,int v){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=v;
    }else{
        int M=L+(R-L)/2;
        if(p<=M)
            update(o<<1,p,v);
        else
            update(o<<1|1,p,v);
        maintain(o);
    }
}
int ql,qr;
Node query(int o){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(ql<=L && R<=qr){
        return Tree[o];
    }
    int M=L+(R-L)/2;
    Node ANS,LC,RC;
    if(ql<=M){
        LC=query(o<<1);
        if(qr>M){
            RC=query(o<<1|1);
            merge(ANS,LC,RC);
            return ANS;
        }else{
            return LC;
        }
    }else{
        RC=query(o<<1|1);
        return RC;
    }
}
int main(){
    int n,m;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&A[i]);
    build_tree(1,1,n);
    int k,a,b;
    Node ans;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&k,&a,&b);
        if(k&1){
            if(a>b)
                swap(a,b);
            ql=a;
            qr=b;
            ans=query(1);
            printf("%d\n",ans.ans);
        }else{
            update(1,a,b);
        }
    }
    return 0;
}