杭电1024 Max Sum Plus Plus状压dp(java)
【摘要】 问题描述
现在我认为你已经在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...
问题描述
现在我认为你已经在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;
}
}
文章来源: bigsai.blog.csdn.net,作者:Big sai,版权归原作者所有,如需转载,请联系作者。
原文链接:bigsai.blog.csdn.net/article/details/79628860
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)