主站
DreamJudge
院校信息
专业题库
模拟考试
机试真题
专业课程
讨论区
兑换中心
登录
注册
上岸
以下题解仅供学习参考使用。
抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在N诺是严格禁止的。
N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。
考小研
2023年8月5日 13:23
DP空间优化O(1)(时间236ms,内存140kb)
P1172
回复 0
|
赞 0
|
浏览 445
#include<cstdio> long a, dp, maxT;//64位机下long是8B,32位机是4B,注意细节 int main() { int n; while (scanf("%d", &n)!=EOF) { scanf("%ld", &a); maxT = dp = a;//初始化 for (int i = 1; i < n; i++) { scanf("%ld", &a); dp = (dp > 0)? (dp + a) : a; if (dp > maxT...
zhourui
2023年4月13日 11:39
1172-动态规划
P1172
回复 0
|
赞 1
|
浏览 1.7k
这一题由于数据的原因一定要用longlong #include<iostream> #include<string> #include<vector> #include<algorithm> #include<string.h> #include <bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n){ long long a[n]; for(int i=0;i<...
Hegel
2023年3月24日 21:20
最大连续子序列O(n)
P1172
回复 0
|
赞 0
|
浏览 1.7k
#include <iostream> using namespace std; int main() { int n; while(cin>>n){ long long *a=new long long[n]; for(int i=0;i<n;i++) cin>>a[i]; long long max=a[0],sum=0; for(int i=0;i<n;i++){ sum+=a[i]; if(sum<0) sum=0; if(sum>max)...
青缘
2022年7月19日 11:57
1172 最大序列合 清华/兰大2019年机试
P1172
回复 0
|
赞 4
|
浏览 4.6k
这题归于动态规划,但是我之前怎么看都觉得是贪心 今天想通了,可以从两种不同的角度来看: 设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
|
赞 0
|
浏览 8.8k
/* * 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...
Ang
2020年4月7日 15:27
用double会有一部分数据过不去,用long long就好了
P1172
回复 0
|
赞 0
|
浏览 12.0k
#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
题目
最大序列和
题解数量
16
发布题解
热门题解
1
1172 最大序列合 清华/兰大2019年机试
2
最大序列和 题解:普通做法 &注意long long AC100%
3
1172-动态规划
4
最大序列和 题解:
5
最大序列和 题解:
6
最大序列和 题解:全改为long long
7
DP空间优化O(1)(时间236ms,内存140kb)
8
最大序列和 题解:
9
最大连续子序列O(n)
10
用double会有一部分数据过不去,用long long就好了