注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

M段最大和的优化  

2009-09-12 11:20:23|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天,我实验了好久就想做的一件事。
有一列数(N个),从中选出M段,使得他们的和最大。

朴素的dp:
复杂度O(N*M)
我想出的算法:
复杂度O(N+MlogN)

朴素的dp:
dp1(i,j)前i个中找j段的最大和
dp2(i,j)前i个中找j段的最大和,且必须保证最后一个数是被选的。
转移方程参见代码

新算法的思想:增量法+线段树
每次找出连续和最大的一段,然后,
把他们统统取反(f[i]=-f[i])

代码:
#include <cstdio>
#define NMax 100000
#define MMax 10000
using namespace std;
struct val{
int v,l,r;
void toMax(int a,int i,int j){
if (v<a){
v=a;l=i;r=j;
}
}
void toMin(int a,int i,int j){
if (v>a){
v=a;l=i;r=j;
}
}
void to0(int i,int j){
v=0;l=i;r=j;
}
};
struct Tnode{
val mn,mx,lx,ln,rx,rn;
int s;
char flag;
};
Tnode tree[262144];
int N,M,A[NMax];
void updatetree(int id,int l,int r){
tree[id].s=tree[id+id+1].s+tree[id+id+2].s;
tree[id].ln=tree[id+id+1].ln;
tree[id].ln.toMin(tree[id+id+1].s+tree[id+id+2].ln.v,
l,tree[id+id+2].ln.r);
tree[id].rn=tree[id+id+2].rn;
tree[id].rn.toMin(tree[id+id+2].s+tree[id+id+1].rn.v,
tree[id+id+1].rn.l,r);
tree[id].lx=tree[id+id+1].lx;
tree[id].lx.toMax(tree[id+id+1].s+tree[id+id+2].lx.v,
l,tree[id+id+2].lx.r);
tree[id].rx=tree[id+id+2].rx;
tree[id].rx.toMax(tree[id+id+2].s+tree[id+id+1].rx.v,
tree[id+id+1].rx.l,r);
tree[id].mn=tree[id+id+1].mn;
tree[id].mn.toMin(tree[id+id+2].mn.v,tree[id+id+2].mn.l,
tree[id+id+2].mn.r);
tree[id].mn.toMin(tree[id+id+1].rn.v+tree[id+id+2].ln.v,
tree[id+id+1].rn.l,tree[id+id+2].ln.r);
tree[id].mx=tree[id+id+1].mx;
tree[id].mx.toMax(tree[id+id+2].mx.v,tree[id+id+2].mx.l,
tree[id+id+2].mx.r);
tree[id].mx.toMax(tree[id+id+1].rx.v+tree[id+id+2].lx.v,
tree[id+id+1].rx.l,tree[id+id+2].lx.r);
}
void buildtree(int id,int l,int r){
if (l==r){
tree[id].mn.to0(l,l-1);tree[id].mx.to0(l,l-1);
tree[id].ln.to0(l,l-1);tree[id].lx.to0(l,l-1);
tree[id].rn.to0(l,l-1);tree[id].rx.to0(l,l-1);
tree[id].s=A[l];tree[id].flag=0;
tree[id].mn.toMin(A[l],l,l);tree[id].mx.toMax(A[l],l,l);
tree[id].ln.toMin(A[l],l,l);tree[id].lx.toMax(A[l],l,l);
tree[id].rn.toMin(A[l],l,l);tree[id].rx.toMax(A[l],l,l);
}else{
buildtree(id+id+1,l,(l+r)>>1);
buildtree(id+id+2,((l+r)>>1)+1,r);
updatetree(id,l,r);
}
}
void reverse(int id){
val t;
t=tree[id].mn;tree[id].mn=tree[id].mx;tree[id].mx=t;
tree[id].mn.v=-tree[id].mn.v;
tree[id].mx.v=-tree[id].mx.v;
t=tree[id].ln;tree[id].ln=tree[id].lx;tree[id].lx=t;
tree[id].ln.v=-tree[id].ln.v;
tree[id].lx.v=-tree[id].lx.v;
t=tree[id].rn;tree[id].rn=tree[id].rx;tree[id].rx=t;
tree[id].rn.v=-tree[id].rn.v;
tree[id].rx.v=-tree[id].rx.v;
tree[id].s=-tree[id].s;
tree[id].flag^=1;
}
void reverse(int id,int l,int r,int b,int e){
if (l>e || r<b)return;
if (b<=l && r<=e)
reverse(id);
else{
if (tree[id].flag){
reverse(id+id+1);
reverse(id+id+2);
tree[id].flag=0;
}
reverse(id+id+1,l,(l+r)>>1,b,e);
reverse(id+id+2,((l+r)>>1)+1,r,b,e);
updatetree(id,l,r);
}
}
int main()
{
scanf("%d %d",&N,&M);
for (int i=0;i<N;i++)scanf("%d",A+i);
buildtree(0,0,N-1);
int b,e,s;
s=0;
for (int i=0;i<M;i++){
s+=tree[0].mx.v;
b=tree[0].mx.l;e=tree[0].mx.r;
reverse(0,0,N-1,b,e);
}
printf("%d\n",s);
getchar();getchar();
return 0;
}
朴素:
#include <cstdio>
#include <string.h>
#define NMax 100000
#define MMax 10000
using namespace std;
int dp1[2][MMax+1];
int dp2[2][MMax+1];
int A[NMax],N,M;
int main()
{
int tmp;
scanf("%d %d",&N,&M);
for (int i=0;i<N;i++)scanf("%d",A+i);
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
for (int i=0;i<N;i++){
for (int j=0;j<=M;j++){
if (j){
dp1[i&1][j]=dp1[i&1][j-1];
tmp=dp1[(i&1)^1][j];
if (tmp>dp1[i&1][j])dp1[i&1][j]=tmp;
tmp=dp1[(i&1)^1][j-1]+A[i];
if (tmp>dp1[i&1][j])dp1[i&1][j]=tmp;
tmp=dp2[(i&1)^1][j]+A[i];
if (tmp>dp1[i&1][j])dp1[i&1][j]=tmp;
}else dp1[i&1][j]=0;
if (j){
dp2[i&1][j]=dp2[i&1][j-1];
tmp=dp2[(i&1)^1][j]+A[i];
if (tmp>dp2[i&1][j])dp2[i&1][j]=tmp;
tmp=dp1[(i&1)^1][j-1]+A[i];
if (tmp>dp2[i&1][j])dp2[i&1][j]=tmp;
}else dp2[i&1][j]=0;
}
}
tmp=0;
for (int i=0;i<=M;i++)
if (tmp<dp1[(N&1)^1][i])tmp=dp1[(N&1)^1][i];
printf("%d\n",tmp);
getchar();getchar();
return 0;
}

  评论这张
 
阅读(850)| 评论(6)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017