HDU-10240Max Sum Plus Plus+动态规划+滚动数组
2024-09-01 07:04:16
Max Sum Plus Plus
题意:题意理解了老半天,这里是说在给定数列中,取m组子数列,不能有重复,使得这些子序列的和最大;
就比如m=2时候,1 /2/-4/5/6.可以不用拿-4的意思;
思路:这道题的思路是动态规划,递推;
状态dp[i][j]
表示有前j个数,组成i组的和的最大值。
决策: 第j个数,要么包含在第i组里面,要么自己独立成组。
其中最后一组包含a[j]。(这很关键)
则状态转移方程为:(在二维图中,就是要么从左边取,要么取上一行的最大值,下式中,左边max是包含在第i组里,右边max是独立成组)
dp[i][j]=max{dp[i][j-1]+a[j],max{dp[i-1][t]}+a[j]} i-1=<t<j-1
此题n数据太大,二维数组开不下,而且三重循环,想到状态转移方程后还是困难重重。
想想,二维数组不行的话,肯定要压缩成一维数组:
因为dp[i-1][t]的值只在计算dp[i][j]的时候用到,那么没有必要保存所有的dp[i][j] for i=1 to m,这样我们可以用一维数组存储。
用pre[ j ]表示 j 之前一个状态 dp[i-1][ ]中1-j之间的最大字段和(不一定包含 a[j] ),然后推dp[ i ][ j ]状态时,dp[ i ][ j ]=max{pre[j-1],dp[j-1]}+a[j];
红色的为了方便理解,其实不存在。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std; const int maxn = +;
const int inf = 0x3f3f3f;
int pre[maxn],dp[maxn],a[maxn];
int n,m;
int main(){
while(~scanf("%d%d",&m,&n))
{
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
dp[]=;
memset(pre,,sizeof(pre));
int mmax;
for(int i=;i<=m;i++)
{
mmax = -inf;
for(int j=i;j<=n;j++)//对于每个i,随着j的增大,maxx越滚越大,(贪心求连续和最大
{
dp[j] = max(dp[j-],pre[j-])+a[j];
pre[j-] = mmax;//把前一轮(j-1)的最大值赋给pre;
//注意这是第二句,因为pre只能在(i+1)轮起作用;
mmax = max(mmax,dp[j]);
}
}
printf("%d\n",mmax);//最后一轮的最大值就是答案。
}
return ;
}
//给了一组数据,不理解就把所有DP打出来,自己手动模拟一遍,这样好理解多了
/* 4 7
1 2 -4 5 6 -8 10
*/
最新文章
- 【BZOJ】【1096】【ZJOI2007】仓库建设
- C# 调用Dll 传递字符串指针参(转)
- Winform ErrorProvider控件使用
- ormlite 多表联合查询
- Redis 代理 twemproxy
- jquery data属性的使用
- Andrew Ng机器学习课程笔记--week10(优化梯度下降)
- 超详细的CentOS7 64位下MySQL5.7安装与配置(YUM)【转发+新创】
- mysql error 1067 invalid default timestamp
- Oracle数据库基础入门《二》Oracle内存结构
- 关于ES6兼容IE 问题记录之一
- OUI启动时的小错误PRVF-0002
- 【Java入门提高篇】Day4 Java中的回调
- HTML页面打印分页标签样式
- Jmeter关联处理
- python中Excel表操作
- 开源Word读写组件DocX介绍与入门
- 从零开始学Linux系统(四)之Vi/Vim操作指令
- java源文件组成部分
- chef语法和案例
热门文章
- ubuntu kylin的桌面崩溃问题
- 原创:微信小程序开发要点总结
- Android Studio项目/Flutter 案例中Gradle报错通用解决方案(包括Unable to tunnel through proxy问题)
- 字符串(String、StringBuffer、StringBuilder)进阶分析
- 定制开发kubernetes流程
- Hadoop 系列(八)—— 基于 ZooKeeper 搭建 Hadoop 高可用集群
- Spring cloud 超时配置总结
- .xxx.sh脚本无法启动,原来都是特殊字符搞的鬼?
- MySQL一键生成实体文件的神器-ginbro
- HTML5 Device Access (设备访问)