「BZOJ2288」「POJ Challenge」生日礼物

2014年5月7日6,9211

Description

ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A₁, A₂, …, A_N. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。

自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？

Input

第1行，两个整数 N (1 ≤ N ≤ 10⁵) 和 M (0 ≤ M ≤ 10⁵), 序列的长度和可以选择的部分。

第2行， N 个整数 A₁, A₂, …, A_N (0 ≤ |A_i| ≤ 10⁴), 序列。

Output

一个整数，最大的和。

Sample Input

5 2
2 -3 2 -1 2

Sample Output

题解

如果数据范围小这题可以dp

f[i][j]表示前i个取j段这样。。

不会做于是膜拜了seter的题解

似乎是贪心的做法

首先将符号相同的一段合并成一个值，为了处理方便一开始可以将序列中的0全部去掉

如 1 3 -1 -2 4 -1 变成 4 -3 4 -1

容易证明最后结果一定是取完整的一段

如果>0的段小于m那么就解决了

如果大于m

将这些段放入堆中按绝对值进行排序

获取堆中最小值将它和周围两段合并，这里要用到双向链表

因为如果这个值是正数，那么相当于不选它了

是负数的话相当于将它左右两段合并，这样都使得选取的段数-1

但是要考虑一个边界的问题

边上的负数不能取，因为就算取了它也不存在左右两段合并

而正数可以取，相当于不选它了

这里纠结了一天。。。代码写太傻逼一直wa

学长20分钟1A了只能跪舔。

以后输入输出都写快速读入吧，似乎很优越

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
struct heap{int v,x,av;}h[200010];
int n,m,a[100010];
int tmp,sz,ans,tot;
int v[100010],cnt;
int next[100010],pre[100010],pos[100010];
inline int read()
{
    char ch=getchar();
	int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
void pushup(int x)
{
    while(h[x].av<h[x>>1].av)
    {
        pos[h[x>>1].x]=x;
        swap(h[x],h[x>>1]);
        x=x>>1;
    }
    pos[h[x].x]=x;
}
void push(int v,int x)
{
    sz++;h[sz].v=v;h[sz].x=x;h[sz].av=abs(v);
    pos[x]=sz;
    pushup(sz);
}
void pushdown(int x)
{
    int to;
    while((x<<1)<=sz)
    {
        to=(x<<1);
        if(to<sz && h[to].av>h[to+1].av)to++;
        if(h[x].av>h[to].av)
        {
            pos[h[to].x]=x;
            swap(h[to],h[x]);
            x=to;
        }
        else break;  
    }
    pos[h[x].x]=x;
}
void del(int x)
{
    h[x].av=inf;
	pushdown(x);
}
void init()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        a[++tmp]=read();
        if(a[tmp]==0)tmp--;
    }
    v[++cnt]=a[1];
    for(int i=2;i<=tmp;i++)
    {
        if((a[i]>0&&a[i-1]>0)||(a[i-1]<0&&a[i]<0))v[cnt]+=a[i];
        else v[++cnt]=a[i]; 
    }
    for(int i=1;i<=cnt;i++)if(v[i]>0){ans+=v[i];tot++;}
    for(int i=1;i<=cnt;i++){next[i]=i+1;pre[i]=i-1;}
    pre[1]=-1;next[cnt]=-1;
}
void solve()
{
    int a,b;heap k;
    for(int i=1;i<=cnt;i++)push(v[i],i);
    while(tot>m)
    {
         k=h[1];
         if(pre[k.x]==-1)
         {
             if(k.v>0){ans-=k.v;del(1);}
             else{del(1);tot++;}
             pre[next[k.x]]=-1;
         }
         else if(next[k.x]==-1)
         {
             if(k.v>0){ans-=k.v;del(1);}
             else{del(1);tot++;}
             next[pre[k.x]]=-1;
         }
         else
         {
             ans-=k.av;
             a=next[k.x];b=pre[k.x];
             pre[k.x]=pre[b];next[pre[b]]=k.x;
             next[k.x]=next[a];pre[next[a]]=k.x;
             h[1].av=h[pos[a]].av+h[pos[b]].av-h[1].av;
             h[1].v+=h[pos[a]].v+h[pos[b]].v;
             pushdown(1);
             del(pos[a]);del(pos[b]);
         }
         tot--;
    }
    printf("%d\n",ans);
}
int main()
{
    init();
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#define inf 0x7fffffff

using namespace std;

struct heap{int v,x,av;}h[200010];

int n,m,a[100010];

int tmp,sz,ans,tot;

int v[100010],cnt;

int next[100010],pre[100010],pos[100010];

inline int read()

{

char ch=getchar();

int f=1,x=0;

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}

return x*f;

}

void pushup(int x)

{

while(h[x].av<h[x>>1].av)

{

pos[h[x>>1].x]=x;

swap(h[x],h[x>>1]);

x=x>>1;

}

pos[h[x].x]=x;

}

void push(int v,int x)

{

sz++;h[sz].v=v;h[sz].x=x;h[sz].av=abs(v);

pos[x]=sz;

pushup(sz);

}

void pushdown(int x)

{

int to;

while((x<<1)<=sz)

{

to=(x<<1);

if(to<sz && h[to].av>h[to+1].av)to++;

if(h[x].av>h[to].av)

{

pos[h[to].x]=x;

swap(h[to],h[x]);

x=to;

}

else break;

}

pos[h[x].x]=x;

}

void del(int x)

{

h[x].av=inf;

pushdown(x);

}

void init()

{

n=read();m=read();

for(int i=1;i<=n;i++)

{

a[++tmp]=read();

if(a[tmp]==0)tmp--;

}

v[++cnt]=a[1];

for(int i=2;i<=tmp;i++)

{

if((a[i]>0&&a[i-1]>0)||(a[i-1]<0&&a[i]<0))v[cnt]+=a[i];

else v[++cnt]=a[i];

}

for(int i=1;i<=cnt;i++)if(v[i]>0){ans+=v[i];tot++;}

for(int i=1;i<=cnt;i++){next[i]=i+1;pre[i]=i-1;}

pre[1]=-1;next[cnt]=-1;

}

void solve()

{

int a,b;heap k;

for(int i=1;i<=cnt;i++)push(v[i],i);

while(tot>m)

{

k=h[1];

if(pre[k.x]==-1)

{

if(k.v>0){ans-=k.v;del(1);}

else{del(1);tot++;}

pre[next[k.x]]=-1;

}

else if(next[k.x]==-1)

{

if(k.v>0){ans-=k.v;del(1);}

else{del(1);tot++;}

next[pre[k.x]]=-1;

}

else

{

ans-=k.av;

a=next[k.x];b=pre[k.x];

pre[k.x]=pre[b];next[pre[b]]=k.x;

next[k.x]=next[a];pre[next[a]]=k.x;

h[1].av=h[pos[a]].av+h[pos[b]].av-h[1].av;

h[1].v+=h[pos[a]].v+h[pos[b]].v;

pushdown(1);

del(pos[a]);del(pos[b]);

}

tot--;

}

printf("%d\n",ans);

}

int main()

{

init();

solve();

return 0;

}

« 「CF425A」Sereja and Swaps 「BZOJ1150」[CTSC2007] 数据备份Backup »

Orchideus

谢谢大神总结

hzwer.com _ Home | http://hzwer.com

「BZOJ2288」「POJ Challenge」生日礼物

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论