P1115题解Hunter_H题解发布于:2019年8月5日P1115题目描述给出一段序列,选出其中连续且非空的一段使得这段和最大。输入格式第一行是一个正整数$N$,表示了序列的长度。第二行包含$N$个绝对值不大于$10000$的整数$A_i$,描述了这段序列。输出格式一个整数,为最大的子段和是多少。子段的最小长度为$1$。解题思路当然你可以暴力枚举$O(n^3)$所以还是动规吧·······$O(n)$设数组$dp[i]$存放的一第$i$个数字为结尾的连续字串和最大的值转移方程式如下:$$dp[i]=max(dp[i-1]+a[i],dp[i])$$代码如下:123456789101112131415161718192021222324#include <iostream>#include <cstdio>using namespace std;int main(){ int n,a[200005],tmp; cin>>n; cin>>tmp; a[1]=tmp; for (int i=2;i<=n;i++) { cin>>tmp; a[i]=max(tmp,a[i-1]+tmp); } int m=-999999999; for (int i=1;i<=n;i++) if (a[i]>m) m=a[i]; cout<<m; return 0;}更新于:2020年1月7日luogu动态规划20190806模拟赛题解一共是6道题目 主要以贪心 动态规划为重点 目前题解更新完前三道 清汤拉面有一天下课,小泉同学、悠、美沙、润相约在一家学校附近的拉面馆。悠、美沙、润都点了清汤拉面。大家都知道,拉面店可以按自己喜...P1716题解原题链接 题目描述观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 12345 7 ...