[Educational Codeforces Round 63 ] D. Beautiful Array (思维+DP)
Educational Codeforces Round 63 (Rated for Div. 2)
D. Beautiful Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array aa consisting of nn integers. Beauty of array is the maximum sum of some consecutive subarray of this array (this subarray may be empty). For example, the beauty of the array [10, -5, 10, -4, 1] is 15, and the beauty of the array [-3, -5, -1] is 0.
You may choose at most one consecutive subarray of aa and multiply all values contained in this subarray by xx. You want to maximize the beauty of array after applying at most one such operation.
Input
The first line contains two integers nn and xx (1≤n≤3⋅105,−100≤x≤1001≤n≤3⋅105,−100≤x≤100) — the length of array aa and the integer xx respectively.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109) — the array aa.
Output
Print one integer — the maximum possible beauty of array aa after multiplying all values belonging to some consecutive subarray xx.
Examples
input
Copy
5 -2
-3 8 -2 1 -6
output
Copy
22
input
Copy
12 -3
1 3 3 7 1 3 3 7 1 3 3 7
output
Copy
42
input
Copy
5 10
-1 -2 -3 -4 -5
output
Copy
0
Note
In the first test case we need to multiply the subarray [-2, 1, -6], and the array becomes [-3, 8, 4, -2, 12] with beauty 22([-3, 8, 4, -2, 12]).
In the second test case we don't need to multiply any subarray at all.
In the third test case no matter which subarray we multiply, the beauty of array will be equal to 0.
题意:
给你一个含有n个数字的数组,和一个整数x
你可以选择一个连续的区间\([l,r]\) 然后\(a[l]\)到\(a[r]\) 每一个数\(a[i]\) 变为\(a[i]*x\)
使改变后的数组的最大连续子段和最大。
思路:
动态规划解决该问题:
设\(dp[i][0]\) 代表到第i个位置,没乘以x的最大子段和。
设\(dp[i][1]\) 代表到第i个位置,结尾是乘以x的最大子段和。
设\(dp[i][2]\) 代表到第i个位置,前面有乘以x的,但是当前结尾是没乘x的最大子段和。
转移方程:
dp[i][0] = max(0ll, dp[i - 1][0]) + a[i];
dp[i][1] = max(max(dp[i - 1][1], dp[i - 1][0]), 0ll) + x * a[i];
dp[i][2] = max(max(dp[i - 1][2], dp[i - 1][1]), 0ll) + a[i];
ans = max(ans, max(dp[i][0], max(dp[i][1], dp[i][2])));
AC 代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline void getInt(int *p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
ll x;
ll a[maxn];
ll dp[maxn][4];
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
gbtb;
cin >> n >> x;
ll sum = 0ll;
repd(i, 1, n) {
cin >> a[i];
sum += a[i];
}
ll ans = 0ll;
ans = max(ans, sum);
repd(i, 1, n) {
dp[i][0] = max(0ll, dp[i - 1][0]) + a[i];
dp[i][1] = max(max(dp[i - 1][1], dp[i - 1][0]), 0ll) + x * a[i];
dp[i][2] = max(max(dp[i - 1][2], dp[i - 1][1]), 0ll) + a[i];
ans = max(ans, max(dp[i][0], max(dp[i][1], dp[i][2])));
}
cout << ans << endl;
return 0;
}
inline void getInt(int *p)
{
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
} else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
最新文章
- 关于form验证的处理片断
- junit4 javaee 5.0 jpa SSH 单元测试问题集锦
- 读&;lt;大数据日知录:架构与算法&;gt;有感
- AVOIR发票的三种作用
- 新手入门 acm 输入输出练习
- SQL Server 表字段值转换成字段名称(二)
- C#遍历窗体控件(原文出自http://www.liangshunet.com/ca/201403/286434593.htm)
- phpcms get标签说明
- VS2012中使用编译的Qt-5.1.1静态库开发程序
- VBA 开发学习--基础语法3
- Javaweb 项目内所有页面都是404问题
- Linux下C++/C的编译调试
- OpenCV和selenum实现点击操作
- c/c++ linux 进程 fork wait函数
- (转)深入理解Java注解类型(@Annotation)
- python类继承的重写和super
- js变量和函数声明的提升(转)
- 关于JEE web项目 Servlet中 “/” 的解释 ;
- web服务端安全之SQL注入攻击
- Linux之Ubuntu切换root su -
热门文章
- OpenGL学习(4)——纹理
- pytest.mark.parametrize()参数化的应用一
- springBoot--组合注解RestController,GetMapping,PostMapping
- tcp与串口透传(select)
- golang的time包:时间字符串和时间戳的相互转换
- [转帖]centos7设置CPU的运行频率为performance
- #【Python】【demo实验23】【练习实例】【 三人比赛顺序问题 】
- 二、python数据类型、字符编码、文件处理
- ArrayList插入1000w条数据的时间比较分析
- 基于APM实现RPC服务和消息队列的指定消费