题意:给出一个 数列 和一个x 可以对数列一个连续的部分 每个数乘以x 问该序列可以达到的最大连续序列和是多少
思路: 不是所有区间题目都是线段树!!!!!!
这题其实是一个很简单的dp
使用的是分类讨论的思想
我们设置dp数组
dp[1][i] 表示一直没有用x 乘过的数组 必须以i 结尾(i可以不选 也就是空序列)的最大连续和
dp[2][i] 表示i是被x乘过的 必须以i 结尾(i可以不选 也就是空序列)的最大连续和
dp[3][i] 表示i之前的数已经有一段被x乘过了 必须以i 结尾(i可以不选 也就是空序列)的最大连续和
本题需要开ll
那么就有状态转移方程为 dp[1][i]=max(dp[1][i-1]+a[i],0) (要么以i结尾向前面选 要么什么都不选)
dp[2][i]=max(dp[1][i-1]+a[i]*x,dp[2][i-1]+a[i]*x,0) (要么首次开始乘x 要么 是中间或者结尾开始乘)
dp[3][i]=max(dp[3][i-1]+a[i],dp[1][i-1]+a[i],0) (要没是从上个前面一段已经乘过的直接加a[i],推过来 ,要么是从还没有乘过x 的直接加a[i]推过来)
Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array 分类讨论连续递推dp的更多相关文章
-
Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array (简单DP)
题目:https://codeforces.com/contest/1155/problem/D 题意:给你n,x,一个n个数的序列,你可以选择一段区间,区间的数都乘以x,然后求出最大字段和 思路: ...
-
Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array(动态规划.递推)
传送门 题意: 给你一个包含 n 个元素的序列 a[]: 定义序列 a[] 的 beauty 为序列 a[] 的连续区间的加和最大值,如果全为负数,则 beauty = 0: 例如: a[] = {1 ...
-
Educational Codeforces Round 63 (Rated for Div. 2) 题解
Educational Codeforces Round 63 (Rated for Div. 2)题解 题目链接 A. Reverse a Substring 给出一个字符串,现在可以对这个字符串进 ...
-
Educational Codeforces Round 63 (Rated for Div. 2) E 带模高斯消元
https://codeforces.com/contest/1155/problem/E 题意 \(f(x)=a_0+a_1x+a_2x^2+...+a_kx^k,k \leq 10,0 \leq ...
-
Educational Codeforces Round 63 (Rated for Div. 2) D dp(最大连续子序列)
https://codeforces.com/contest/1155/problem/D 题意 一个n个数的数组\(a[i]\),可以选择连续的一段乘x,求最大连续子序列的值 题解 错误思路:贪心, ...
-
Educational Codeforces Round 63 (Rated for Div. 2) B. Game with Telephone Numbers 博弈思维+模拟+贪心思维
题意:博弈题面 给出一个数字序列 (>=11) 有两个人任意删除数字 直到 数字只剩下11位 如果删除后的数字串开头是8那么就是第一个赢 否则就是第二个人赢 第一个人先手 数字序列一定是奇 ...
-
Educational Codeforces Round 63 (Rated for Div. 2) C. Alarm Clocks Everywhere gcd
题意:给出一个递增的时间序列a 给出另外一个序列b (都是整数) 以b中任选一个数字作为间隔 自己从1开始任选一个时间当成开始时间 输出选择的数字标号以及 开始时间 思路 直接求间隔的公共gc ...
-
Educational Codeforces Round 63 (Rated for Div. 2)
传送门 A. Reverse a Substring 题意: 给你一串 s,让你判断能否通过反转区间[l,r]的元素,使得反转后的串的字典序小于 s: 如果能,输出 "YES",并 ...
-
Educational Codeforces Round 56 (Rated for Div. 2) D. Beautiful Graph 【规律 &;&; DFS】
传送门:http://codeforces.com/contest/1093/problem/D D. Beautiful Graph time limit per test 2 seconds me ...
随机推荐
-
【C++面试】常考题复习:排序算法
// Sort.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <stdlib.h> /*********** ...
-
UIColor-Hex-Swift
// // UIColorExtension.swift // HEXColor // // Created by R0CKSTAR on 6/13/14. // Copyright (c) 2014 ...
-
Dockerfile的书写规则及指令使用方法
Dockfile是一种被Docker程序解释的脚本,Dockerfile由一条一条的指令组成,每条指令对应Linux下面的一条命令.Docker程序将读取Dockerfile,根据指令生成定制的ima ...
-
[SDOI2016]硬币游戏
题目描述 Alice 和 Bob 现在在玩的游戏,主角是依次编号为 1 到 n 的 n 枚硬币.每一枚硬币都有两面,我们分别称之为正面和反面.一开始的时候,有些硬币是正面向上的,有些是反面朝上的.Al ...
-
webservlce 的各个属性
[WebMethod(Description = "我是可见的", MessageName = "GetAboutIntroduction")]//有这个标志的 ...
-
C/C++遍历二维数组,列优先(column-major)比行优先(row-major)慢,why?
C/C++遍历二维数组,列优先(column-major)比行优先(row-major)慢,why? 简单粗暴的答案:存在Cache机制! 稍微啰嗦一点:CPU访问内存(读/写,遍历数组的话主要是读) ...
-
【Java】NO.80.Note.1.Java.1.001-【Java 各种特性概念】
1.0.0 Summary Tittle:[Java]NO.80.Note.1.Java.1.001-[Java 各种特性概念] Style:Java Series:Java Since:2018-0 ...
-
Bootstrap关闭当前页
function doBack() { var index = parent.layer.getFrameIndex(window.name); parent.lay ...
-
Core Java Fundation
http://www.cnblogs.com/cmfwm/p/7671188.html http://blog.csdn.net/fuckluy/article/details/50614983 ht ...
-
Echarts使用及动态加载图表数据 折线图X轴数据动态加载
Echarts简介 echarts,缩写来自Enterprise Charts,商业级数据图表,一个纯JavaScript的图表库,来自百度...我想应该够简洁了 使用Echarts 目前,就官网的文 ...