A Mini Locomotive(动态规划 01)

Stella981
• 阅读 538

 /*

 题意:选出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

#include

#include

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;

}

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
2年前
POJ3274(哈希)
第一篇博客emmm根据kuangbin  dalao的poj刷题指南做的一道不是很简单的哈希题目题意是求特征之和相同的第i头牛到第j头牛的max(ji)一开始是没有思路的,苦思冥想半天然后(看了题解以后)手推公式:num\i\\1\...num\j\\1\num\i\\2\....num\j\
待兔 待兔
4天前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
先知 先知
3年前
java实现九九乘法表的输出
这是小学二年级令人难忘的坷如今以java程序的行式展示,真不戳!publicclassscore{publicstaticvoidmain(Stringargs){inti,j;for(i1;i<9;i){for(j1;j<9;j
Karen110 Karen110
3年前
人工智能数学基础-线性代数4:矩阵及矩阵运算
一、矩阵定义矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合,定义如下:由m×n个数aij排成的m行n列的数表称为m行n列的矩阵,简称m×n矩阵。记作:这m×n个数称为矩阵A的元素,简称为元,数aij位于矩阵A的第i行第j列,称为矩阵A的(i,j)元,以数aij为(i,j)元的矩阵可记为(aij)或(aij)m×n,m×
Wesley13 Wesley13
2年前
JAVA 中数组的几种排序方法
1、数组的冒泡排序publicvoidbubbleSort(inta){intna.length;for(inti0;i<n1;i){for(intj0;j<n1;j)
Stella981 Stella981
2年前
Codeforces 1208F Bits And Pieces 位运算 + 贪心 + dp
题意:给你一个序列a,问a\i\^(a\j\&a\k\)的最大值,其中i<j<k。思路:我们考虑对于每个a\i\求出它的最优解。因为是异或运算,所以我们从高位向低位枚举,如果这一位a\i\是0,我们就在a\i\的右边找两个位置让它们按位与起来这位是1。那么,我们贪心的保留可以通过按位与凑出某个二进制数的最靠右的两
Wesley13 Wesley13
2年前
TZOJ 2722 Matrix(树状数组区间取反单点查询)
描述GivenanN\NmatrixA,whoseelementsareeither0or1.A\i,j\meansthenumberintheithrowandjthcolumn.InitiallywehaveA\i,j\0(1<i,j<N).
Stella981 Stella981
2年前
Forrester机器学习报告发布,腾讯云跃居第一阵营
  !(https://nimg.ws.126.net/?urlhttp%3A%2F%2Fdingyue.ws.126.net%2F2020%2F1016%2Fecdc1f59j00qi98j7000od200u000fpg00it009u.jpg&thumbnail650x2147483647&quality80&typejpg)  A
Wesley13 Wesley13
2年前
2020CCPC长春站部分题解
F题dsuontree维护一个数组t\\\\\\。t\i\\j\\k\表示当前子树内a\u\i且u的第j位是k的u的个数。!(https://imgblog.csdnimg.cn/20201109122529290.png)这个东西没办法直接维护的,但是对于!j(https://private.cod