P1172 最大序列和 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2022年7月19日 11:57

1172 最大序列合清华/兰大2019年机试

P1172

回复 0 | 赞 8 | 浏览 6.1k

这题归于动态规划，但是我之前怎么看都觉得是贪心今天想通了，可以从两种不同的角度来看：设dp[i]是以下标为i的元素为结尾的序列的最大合值 dp角度：遍历到第i个元素时，两种选择：要么选择第i个元素（dp[i-1]+list[i]），要么不选（之前的序列断开，重新开始计数）（list[i]），取最大值状态转移方程： dp[i]=max( dp[i-1]+list[i] , list[i] ); 最后再求出dp[n]中的最大值贪心角度：如果之前的序列合为负值，则说明对之后的序列合没有贡...

2021年2月18日 18:31

用int类型数组储存数据，部分测试数据溢出，改为long long就好

P1172

回复 0 | 赞 1 | 浏览 10.4k

/* * Description: 最大序列和 (http://noobdream.com/DreamJudge/Issue/page/1172/) * Author: 鱼翔浅底 * Date: 2021-02-18 16:54:58 */ #include <cstdio> #include <cstdlib> using namespace std; //计算最大序列和 long long MaxSequenceSum(long long S[], int N) { long long ans = S...

2020年4月7日 15:27

用double会有一部分数据过不去，用long long就好了

P1172

回复 0 | 赞 0 | 浏览 13.5k

#include<bits/stdc++.h> using namespace std; int const maxn = 1e6 + 1; long long dp[maxn]; int main(){ int n; while(cin>>n){ fill(dp,dp+maxn,0); long long first; cin>>first; dp[0] = first; long long ans = first; ...

1
2
3

题目最大序列和

题解数量23

发布题解在线答疑

热门题解

1 最大序列和题解：dp思路

2 最大序列和(75%的巨坑！！！（贪心）)题解：

3 最大序列和题解：动态规划

4 最大序列和题解：

5 最大序列和题解：

6 1172 最大序列合清华/兰大2019年机试

7 最大序列和题解：普通做法 &注意long long AC100%

8 最大序列和题解：全改为long long

9 最大序列和题解：dp的核心:吸收or重构

10 最大序列和题解：