Educational Codeforces Round 123 (Rated for Div. 2)C、Increase Subarray Sums(求前缀和)

发布时间:2023-10-05 09:30

子段连续
求最大子段和(dp)

int Maxsum(int n,int *x)
{
    int sum = 0,b = 0,ll,rr;
    for(int i = 1;i <= n;i++)
    {
        if(b > 0)
            {b += x[i];}
        else
            {b = x[i];}
        if(b > sum)
            {sum = b;}
    }
    return sum;
}

C、Increase Subarray Sums
求各个长度时的最大子段和,x需要加的个数分别加到对应长度的子段和上使得sum最大。

#include
using namespace std;
typedef long long ll;
ll b[5005],dp[5005];
int main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--){
		ll n,x;
		cin>>n>>x;
		for(int i=1;i<=n;i++) cin>>b[i],b[i]=b[i]+b[i-1],dp[i]=-1e18;//前缀和
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
				dp[j-i+1]=max(dp[j-i+1],b[j]-b[i-1]);//各个长度的最大子段和
		for(int i=0;i<=n;i++){
			ll mx=0;
			for(int j=0;j<=n;j++)
				mx=max(mx,dp[j]+min(i,j)*x);//x的个数分别加到对应长度的最大子段上
			cout<<mx<<\' \';
		}
		cout<<\'\\n\';
	} 
    return 0;
}

你可能感兴趣的

相关推荐

「阿里云 RocketMQ 系列公开课」重磅来袭!

LeetCode 题解 | 1. 两数之和 Javascript 版

目标检测—R-CNN、Fast R-CNN和Faster R-CNN

局域网安全攻防

PostgreSQL下的SQL Shell(psql)工具

SaaS应用:实现企业数字化转型的最佳途径

强化学习入门笔记(一)——莫烦Python

PyTorch模型参数初始化

【宫水三叶的刷题日记】468. 验证IP地址

零基础JavaScript学习【第六期】

从零搭建vite + vue3.0 + vuex + router + sass/less + naive

在IDEA中配置Maven

深度之眼(五)——Python组合数据类型

mysql split函数用逗号分隔的实现

直面秋招!高级Java开发面试解答,写的太详细了

性能提升19倍,DGL重大更新支持亿级规模图神经网络训练

机器学习的路,感觉很受用

Python利用字典和列表实现学生信息管理系统

在vue2 中使用 tailwindcss的方法 亲测可用

最快最好用的数据增强库「albumentations」 一文看懂用法

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号