• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

题意:

将数组分成任意的子段。对于每个分段,如果分段之和为正,则其值为分段长度;如果为负,则为分段长度的倒数;如果为0,则值为0。求最大值之和。

思路:

如果\(a_i\le 0\),最好\(a_i\)成为自己的段落,长度为1。

dp .两个选项:

\(dp(i)=dp(i-1) sgn(a_i)\)

\(DP(I)=I \ max \ limits _ { s _ is _ j } \ {-j DP(j)\ } \)

对于第二种情况,\(s[]\)被离散化,最大前缀值由树数组维护。

注意:树型数组应该初始化为负无穷大,ask()函数也应该是负无穷大。\(s_0\)也要算。

void sol() {

CIN n;for(int I=1;I=n;CIN a

for(int I=1;I=n;I)s=s[I-1]a

//离散化,小心计数为0

vectorll ALL(s,s ^ 1n);sort(all(ALL))、ALL.erase(unique(all(ALL))、ALL . end());

for(int I=0;I=n;i ) ord=lower_bound(all(ALL),s)-ALL . begin()1;

//dp,记住0

fill(tr,tr ^ 1n,-INF);add(order[0],0);

for(int I=1;I=n;i ) {

f=f[I-1]-(a0)(a0);

f=max(f,ask(ord-1)I);

add(order,f-I);

}

cout f[n]endl;

}

Link to comment
Share on other sites