杭电1024 Max Sum Plus Plus状压dp(java)

简介: 现在我认为你已经在Ignatius.L的“最大总和”问题中得到了AC。为了成为一名勇敢的ACMer,我们总是向更难挑战的问题挑战自我。现在你面临着一个更困难的问题。

问题描述



现在我认为你已经在Ignatius.L的“最大总和”问题中得到了AC。为了成为一名勇敢的ACMer,我们总是向更难挑战的问题挑战自我。现在你面临着一个更困难的问题。

给定连续的数字序列S1,S2,S3,S4 … Sx,… Sn(1≤x≤n≤1,000,000,-32768≤Sx≤32767)。我们定义了函数和(i,j)= Si … Sj(1≤i≤j≤n)。


现在给定一个整数m(m> 0),你的任务是找到m对i和j,它们使sum(i1,j1) sum(i2,j2) sum(i3,j3) … sum (im,jm)maximal(ix≤iy≤jx或者ix≤jy≤jx是不允许的)。


但我很懒惰,我不想写一个专门的判断器模块,所以你不必输出m对i和j,只输出sum(ix,jx)的最大和(1≤x ≤m)。 ^ _ ^


输入


每个测试用例将以两个整数m和n开始,随后是n个整数S1,S2,S3 … Sn。

处理到文件的结尾。


产量


在一行中输出上述最大和。


示例输入


1 3 1 2 3

2 6 -1 4 -2 3 -2 3


示例输出


6

8


这题刚开始不明白,后来看了别人的思路。用dp[m][n]自己做出来但是数组太大,后来又继续学习,发现人家把多维的压缩成二维,看了好久才看明白。。


首先 value[i][j]表示以第j个元素结尾的i对最大,(dp经常处理的是以谁为结尾)

dp[i][j]表示第j元素中要求的最大。


i>j时:

value[i][j] = max( value[i][j-1] a[j], max( value[i-1][t] (i-1<=t <= j-1) a[j]))可以理解。


简单而说value[i][j] = max(i对以第j-1结尾 a[j],i-1对前j-1个找最大 a[j]);(直接接上,和最后一个单独取)


那么 value[i][j]=max(value[i][j-1] a[j],dp[i-1][j-1] a[j]);


然而 dp[i][j]=max(以第j个结尾的最大,不以第j个结尾)。


可以表示为:dp[i][j]=max(value[i][j],dp[i][j-1])


最终得到方程组:


value[i][j]=max(value[i][j-1] a[j],dp[i-1][j-1] a[j]);
dp[i][j]=max(value[i][j],dp[i][j-1]) ;


dp[i][j]只和当前的 dp[i][]和 value[i][]有关,和前面的数据无关,而value[i][]只和value[i][]和dp[i-1][]有关,可以想一下,每一次i循环,我求这组的数据value要重新赋值,并且和dp[i][]层,和dp[i-1][]层有关,那么我就可以直接用value[j]表示当前i层的以j为结尾的最大。同理第i层的dp求要用到前面的dp[i][]和上一层的dp[i-1][];那么可以简写为 dp[i%2][j]表示当前i的以j之中的最大。


简写为:


value[j]=max(value[j-1] a[j],dp[(i-1)%][j-1] a[j]);
dp[i%2][j]=max(value[j],dp[i%2][j-1]) ;


打个比方:爸爸妈妈儿子女儿洗澡,一个人要一个桶泡,你有钱可以买四个桶一人一个洗澡,你没钱就爸爸先用,然后妈妈,女儿,儿子用。


附上代码如下:


import java.util.Scanner;
public class 杭电1024 {
  public static void main(String[] args) {        
         Scanner sc=new Scanner(System.in);
         while(sc.hasNext())
         {
           int m=sc.nextInt();//对数
           int n=sc.nextInt();//元素个数
           int a[]=new int[n 1];//元素值
            int dp[][]=new int[2][n 1];
            int value[]=new int[n 1];
        int q=0;int max=0;
           for(int i=1;ii)
               {
                 value[j]=max(dp[(i-1)%2][j-1] a[j],value[j-1] a[j]);//
                 dp[i%2][j]=max(dp[i%2][j-1],value[j]);//
               }
             }
             }          
           System.out.println(dp[m%2][n]);
         }
    }
    private static int max(int i, int value) {      
      return i>value?i:value;
    }
  }
目录
相关文章
|
8月前
|
SQL XML JavaScript
【若依Java】15分钟玩转若依二次开发,新手小白半小时实现前后端分离项目,springboot+vue3+Element Plus+vite实现Java项目和管理后台网站功能
摘要: 本文档详细介绍了如何使用若依框架快速搭建一个基于SpringBoot和Vue3的前后端分离的Java管理后台。教程涵盖了技术点、准备工作、启动项目、自动生成代码、数据库配置、菜单管理、代码下载和导入、自定义主题样式、代码生成、启动Vue3项目、修改代码、以及对代码进行自定义和扩展,例如单表和主子表的代码生成、树形表的实现、商品列表和分类列表的改造等。整个过程详细地指导了如何从下载项目到配置数据库,再到生成Java和Vue3代码,最后实现前后端的运行和功能定制。此外,还提供了关于软件安装、环境变量配置和代码自动生成的注意事项。
7823 6
|
9月前
|
Java
杭电 OJ 1010-1019 Java解法(未更新完毕)
杭电 OJ 1010-1019 Java解法(未更新完毕)
39 1
|
9月前
|
Java
杭电acm1201 18岁生日 Java解法 时间类
杭电acm1201 18岁生日 Java解法 时间类
42 0
|
9月前
|
算法 Java
杭电 OJ 1000-1009 Java解法
杭电 OJ 1000-1009 Java解法
36 0
|
9月前
|
Java
杭电acm2018 母牛的故事 Java解法 经典递归
杭电acm2018 母牛的故事 Java解法 经典递归
50 0
|
9月前
|
Java BI
杭电acm1013 Digital Roots 数字根 Java解法 高精度
杭电acm1013 Digital Roots 数字根 Java解法 高精度
43 0
|
9月前
|
网络安全 Nacos
对于修改后Nacos端口,连接超时,java.util.concurrent.TimeoutException: Waited 3000 milliseconds (plus 5 millisec
对于修改后Nacos端口,连接超时,java.util.concurrent.TimeoutException: Waited 3000 milliseconds (plus 5 millisec
|
10月前
|
人工智能 IDE Java
软件测试/人工智能|Java Edit Plus 安装与配置指南
软件测试/人工智能|Java Edit Plus 安装与配置指南
|
Java 关系型数据库 数据库连接
探索Java中的MyBatis Plus注解 @DbType:灵活处理数据库类型
在数据库操作中,不同的数据库系统可能具有不同的数据类型,如MySQL、Oracle、SQL Server等,这就需要我们在操作中处理不同的数据库类型。MyBatis Plus作为一款强大的ORM框架,提供了注解 `@DbType`,使得开发者能够更加灵活地处理数据库类型,从而在多数据库支持下轻松切换。本文将详细介绍 `@DbType` 注解的用法及其在持久层开发中的应用。
1663 1
|
Java 数据库连接 数据库
解析Java中的MyBatis Plus注解 @FieldFill:优雅处理字段填充
在数据库操作中,有些字段的值在插入或更新时需要自动填充,比如创建时间、更新时间等。MyBatis Plus作为一款强大的ORM框架,提供了注解 `@FieldFill`,使得开发者能够更加灵活地处理字段的自动填充,从而减少了重复的代码编写。本文将详细介绍 `@FieldFill` 注解的用法及其在持久层开发中的应用。
2907 1

热门文章

最新文章