不是VIP会员,不能显示答案

题目解答

题目:
最大子段和

给定一个整数序列a[0],a[1],...,a[n-1],你可以选择k个位置加x,使得最大子段和最大。你需要对于每个0≤k≤n,求出最大子段和的最大值。

最大子段和定义为选择0≤1≤r≤n, a[l]+a[l+1]+...+a[r-1] (选择l=r时即为0)的最大值。

1≤n≤5000, 0≤x≤10^5,|a[il|≤10^5。

输入格式:

第一行两个整数n,x。

第二行n个整数a[0],a[1],...,a[n-1].

输出格式: n+1行,第i行一个整数,表示k=i-1时的答案。

输入样例:

3 5

-2 -7 -1



输出样例

0

4

4

5



提示:假设固定k,对于一对l,r,最大的和为a[l]+a[l+1]+...+a[r-1]+min(k,r-1)*x.

枚举k,对于r-1<=k和r-1>=k的分别计算最大值即可。

程序:



#include <bits/stdc++.h>

using namespace std;

int n,x,a[5000], sum[5001], ans [5001];

int main(){

cin>> n>> x;

for (int i=0; i<n; ++i) cin>>a[i];

for (int i=0; i<n; ++i) sum[i+1]=__(1)__;

for (int l=0; l<=n; ++l)

for(int r=1; r<=n; ++r)

ans[r-1] = max(ans[r-1], __(2)__);

for (int i=1; i<=n; ++i)

ans[i] = max (ans[i], __(3)__);

for (int k=0; k<=n; ++k){

int pre_min =0;

for (int i=k; i<=n; ++i){

pre_min = min(pre_min, __(4)__);

ans[k] = max(ans[k],__(5)__);

}

}

for (int i=0; i<=n; ++i) cout << ans[i]<<"\n";

}


选择题

1) ⑴处应填( )。

2) ⑵处应填( )。

3) ⑶处应填( )。

4) ⑷处应填( )。

5) ⑸处应填( )。
考点:
分析:
解答:
评论:
老师: