文档章节

A Mini Locomotive(动态规划 01)

1
 1944864971
发布于 2016/07/24 11:59
字数 340
阅读 7
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

 /*
 题意:选出3个连续的 数的个数  为K的区间,使他们的和最大
分析: dp[j][i]=max(dp[j-k][i-1]+value[j],dp[j-1][i]);
 
dp[j][i]:从j个数种选出i个连续区间  数值的最大和
value[j]:第j个区间内的数的和
和背包有点像,但要活用
 
*/
 
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp[50005][4];
 
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
 
 
 
        int n;
        scanf("%d",&n);
        int a[n+1],sum[n+1];
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        memset(sum,0,sizeof(sum));
 
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];//前缀和,用于求连续k个数的和
        }
 
 
 
        int k=0;
        scanf("%d",&k);
        int value[n+1];
        memset(value,0,sizeof(value));
        for(int i=1; i<=k; i++)
            value[i]=value[i-1]+a[i];
        for(int i=k+1; i<=n; i++)
            value[i]=sum[i]-sum[i-k];//连续k个数的和,value[i]代表区间长度为k的第i个区间
 
 
 
        for(int j=k; j<=n; j++)
            for(int i=1; i<=3; i++)
                dp[j][i]=max(dp[j-k][i-1]+value[j],dp[j-1][i]);//从j个数中选出i个区间,若选第i个区间,就相当于从前(j-k)个数中选出(i-1)个区间的基础上再加此区间(value[j]),若不选就是相当于在(j-1)个数中选i个区间
 
 
 
            printf("%d\n",dp[n][3]);
 
 
 
    }
 
    return 0;
}

本文转载自:http://www.cnblogs.com/aaaadengchaochao/p/4993163.html

1
粉丝 0
博文 57
码字总数 0
作品 0
郑州
私信 提问
Rails开发工具--Locomotive

Locomotive是一个很简洁的工具,可以帮助你在Mac OS X下开发Ruby on Rails应用。使用Locomotive来进行Rails开发,你就不用花数小时来解决损坏的类库,编译出错,不兼容等问题,而直接可以进行...

匿名
2009/04/01
1K
0
前端与算法-动态规划之01背包问题浅析与实现

去年因为工作中的某个应用场景,需要使用到动态规划,为此花了些时间啃了啃背包算法 为啥去年的东西,今年才写粗来,也许大概是懒吧 动态规划 Dynamic Programming 先简单说下什么是动态规划...

小黎也
2018/07/31
0
0
Node.js 的MVC框架--Locomotive JS

Locomotive 是个强大的 Node.js 的 MVC 框架,支持 RESTful ;可以无缝连接任何数据库和模版引擎。Locomotive 是在 Express 的基础上建立的,保持了 Node.js 强大而简单的功能。...

叶秀兰
2014/02/25
1K
0
动态规划——背包问题(01背包、完全背包、多重背包)

参考: 背包九讲——哔哩哔哩 背包九讲 01背包问题 01背包问题 描述: 有N件物品和一个容量为V的背包。 第i件物品的体积是vi,价值是wi。 求解将哪些物品装入背包,可使这些物品的总体积不超...

pandaWaKaKa
08/25
0
0
算法:Dynamic Programing

一、动态规划干嘛的 二、可以解决哪些问题 动态规划一般可分为:线性动规,区域动规,树形动规,背包动规四类。 线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等; 区域动规:石子...

猫咪要感冒
2016/10/09
1
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么面试必问线程状态?你的回答满分了吗

看很多同学的面经、网上的面试资料,都不约而同的提到了一个基础问题:“你知道线程有几种状态吗?状态之间的扭转是怎样的?”,有准备的同学都知道有五种:New(新建)、Runnable(可运行)...

Z_J_H
29分钟前
4
0
如何保障云上数据安全?一文详解云原生全链路加密

点击下载《不一样的 双11 技术:阿里巴巴经济体云原生实践》 本文节选自《不一样的 双11 技术:阿里巴巴经济体云原生实践》一书,点击上方图片即可下载! 作者 李鹏(壮怀)阿里云容器服务高...

阿里巴巴云原生
29分钟前
3
0
获取数组的第一个元素

我有一个数组: array( 4 => 'apple', 7 => 'orange', 13 => 'plum' ) 我想获得此数组的第一个元素。 apple 预期结果: apple 一个要求: 它不能通过引用传递来完成 ,所以array_shift不是一......

javail
31分钟前
4
0
哈希情史知多少

<p align="right">——日拱一卒,不期而至!</p> 简介 hash是我们工作中经常听到的词,比如哈希表、哈希函数、hashCode、HashTable、HashMap等等,那么它们之间到底有怎样的爱恨情仇呢?来一...

彤哥读源码
37分钟前
4
0
SpringCloud 学习(5) --- Zuul(一)基本概念、配置

[TOC] Spring Cloud eureka:注册中心 服务端:提供注册 客户端:进行注册 ribbon:负载均衡(集群) Hystrix:熔断器,执行备选方案 Feign:远程调用 Zuul:网关,统一入口。 1.1、一夫当关,...

庭前云落
39分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部