SweetGame

NC223579. SweetGame

描述

Sept 有 $n$ 颗糖，吃第 $i$ 颗糖会得到 $a_i$ 的甜度，现在他想请 Cindy 吃掉所有的糖。
但是，如果要吃第 $k$ 颗糖，必须在吃它之前或之后吃完第 $k+1\sim n$ 颗糖。
换句话说，当 $k<i,j\le n$ 时，Cindy 不能在吃第 $k$ 颗糖前吃糖 $i$ ，而在吃第 $k$ 颗糖后吃糖 $j$ 。
每颗糖的甜度都会随着时间的变化而减少或增多，每过 $1$ 个单位时间，第 $i$ 颗糖的甜度会变化 $\Delta d_i$ 。
Cindy 每吃一个棒棒糖需要 $1$ 个单位时间（在这个单位时间内，Cindy 吃的糖的甜度不会发生变化）。
Sept 当然希望 Cindy 能获得最大的甜度，求这个最大甜度的值。
注意：Cindy 必须连续不断地吃掉这 $n$ 个棒棒糖。

输入描述

第一行一个整数  ，表示糖的数量。
第二行  个整数 ，表示每颗糖的甜度。
第三行  个整数 ，表示每颗糖每  个单位时间的甜度会增加 。

输出描述

仅一行一个整数，即 Cindy 能获得的最大甜度。

示例1

输入:

4
1 1 1 1
2 -3 -1 1

输出:

说明:

对于这个样例， $\tt{2\ 3\ 4\ 1}$ 是最佳的顺序。按照此顺序，Cindy 得到的甜度依次是 $1,0,3,7\$ ，总甜度是 $1+0+3+7=11\$ 。
该顺序也符合 Sept 的要求。

示例2

输入:

3
11 45 14
2 -1 1

输出:

说明:

对于这个样例， $\tt{2\ 3\ 1}$ 是最佳的顺序。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 62ms, 内存消耗: 2480K, 提交时间: 2022-09-25 15:24:16

#include<bits/stdc++.h>
#define int long long 
const int maxn=2e5+100;
using namespace std;
int n,a[maxn],d[maxn],ans,sum;
signed main(){
    cin >> n;
    for(int i=1;i<=n;++i) cin >> a[i];
    for(int i=1;i<=n;++i) cin >> d[i];
    for(int i=n;i>=1;--i){
        ans=max(ans+sum+a[i],a[i]+ans+(n-i)*d[i]);
        sum+=d[i];
    }
    cout << ans << endl;
    return 0;
}

C++ 解法, 执行用时: 28ms, 内存消耗: 1400K, 提交时间: 2021-08-28 21:05:52

#include<bits/stdc++.h>
using namespace std;
int n,d[200010],s[200010];
long long ans;
int main(){
	scanf("%d",&n);
	for(int i=1,a;i<=n;i++)scanf("%d",&a),ans+=a;
	for(int i=1;i<=n;i++)scanf("%d",&d[i]);
	for(int i=n;i;i--)s[i]=d[i]+s[i+1];
	for(int i=1;i<=n;i++)ans+=max(d[i]*(n-i),s[i+1]);
	return printf("%lld",ans),0;
}

上一题

下一题

详情