《Tzoj-3927》dp思路
【《Tzoj-3927》dp思路】题意：给你一个环形序列,让你求最大连续子序列和.
解法：环形的最大连续子序列和问题
一开始我的思路是化环为链,然后去dp,但是这样就不能保证有没有重复。
如果要保证没有重复。
那就需要去枚举长度,这样时间复杂度就会升到n^2。
正解思路：
首先这个子序列肯定分为两种情况：
1.跨过了首尾.
2.没有跨过首尾.
对于2我们只需要传统的dp就行了.即普通地求最大连续子序列和
对于1这种情况,我们可以求得最小的连续子序列,这样我们用序列总和减去它,那就是最大的了.
如果求最小的连续子序列：我们可以先将序列的每个数取反,然后就变成了求最大连续子序列。
然后用总的去减去这个和的相反数（其实就是加上这个和）
对于这两种情况我们比较下哪个更大,然后输出.
需要注意的是,当这个序列全是负数时,我们第二种情况会是最小的负数,但是第一种情况我们计算出来会是0.
所以我们需要在输入后判断是不是全是负数,如果全是负数,我们就不考虑第一种情况了.（注意数据会爆longlong）
LL a[N],dp[N];
int main()
{
int t,n;
sd(t);
while(t--)
{
LL sum = 0;
int cnt = 0;
sd(n);
for(int i=0;
i<=n;
++i) dp[i] = 0;
for(int i=1;
i<=n;
++i)
{
sld(a[i]),sum += a[i];
if(a[i] < 0) cnt++;
}
LL ans = -INF;
for(int i=1;
i<=n;
++i)
{
dp[i] = max(dp[i-1],LL(0))+a[i];
ans = max(ans,dp[i]);
a[i] = -a[i];
}
if(cnt == n)
{
plr(ans);
continue;
}
LL temp = -INF;
for(int i=0;
i<=n;
++i) dp[i] = 0;
for(int i=1;
i<=n;
++i) dp[i] = max(dp[i-1],LL(0))+a[i],temp = max(temp,dp[i]);
LL t = sum+temp;
printf("%lld\n",ans>=t?ans:t);
}
system("pause");
return 0;
}推荐阅读
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 《跨界歌手》:亲情永远比爱情更有泪点
- 诗歌:|诗歌: 《让我们举起世界杯，干了！》
- 期刊|期刊 | 国内核心期刊之（北大核心）
- 《魔法科高中的劣等生》第26卷（Invasion篇）发售
- 人间词话的智慧
- 《一代诗人》37期，生活，江南j，拨动心潭的一泓秋水
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术
- 书评——《小行星》