博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu1024 最大m子串和
阅读量:4840 次
发布时间:2019-06-11

本文共 809 字,大约阅读时间需要 2 分钟。

题意:给一个长度为n的序列,找出m个不相交子串的和的最大值

思路:dp[i][j]表示取第j个数,并且前j个数分成i个区间的最大值,状态转移方程为 dp[i][j]=max(dp[i][j-1]+a[j], dp[i-1][k]+a[j])(k=i-1 i i+1 ... j-1 ),dp[i][j-1]+a[j]表示前j-1个分成i个区间并且取了a[j-1],那么在a[j]取的情况下,区间数没有增加,dp[i-1][k]表示在由i-1个区间组成的答案中加入a[j],区间数+1,这里注意一点,状态转移的时候j是从j=i开始遍历的,所以就会出现一个状态 dp[i][i-1] ,这是不可能的,要初始化为-inf,然后就是时间和空间上面的优化了,空间上面,由于每次dp状态只与上一个状态有关,所以可以用滚动数组优化,空间上对k这一维进行优化,从状态转移方程不难看出dp[i-1][k]是在找上一个状态中第二维范围为i-1到j-1的最大值,这里可以每次处理出O(1)求最大值

AC代码: 

#include "iostream"#include "iomanip"#include "string.h"#include "stack"#include "queue"#include "string"#include "vector"#include "set"#include "map"#include "algorithm"#include "stdio.h"#include "math.h"#pragma comment(linker, "/STACK:102400000,102400000")#define bug(x) cout<
<<" "<<"UUUUU"<

 

转载于:https://www.cnblogs.com/max88888888/p/7668275.html

你可能感兴趣的文章
杭电acm2099
查看>>
Linux GCC常用命令
查看>>
拷贝变换3字节像素到4字节内存
查看>>
PythonDay01
查看>>
Oracle数据库的JDBC衔接
查看>>
运用 KCheckGmail 监视 Gmail
查看>>
asp.net core mvc 读取appsettings.config中文乱码问题
查看>>
asp.net 的log4net的helper类
查看>>
shell编程
查看>>
2018上IEC计算机高级语言(C)作业 第1次作业
查看>>
hdu 1753
查看>>
return ;
查看>>
td在relative模式下,IE9不显示border
查看>>
7-内置数据结构
查看>>
version control(版本控制)
查看>>
FutureTask
查看>>
JDBC的元数据
查看>>
Intel CPU参数查询网站
查看>>
JQuery - Ajax和Tomcat跨域请求问题解决方法!
查看>>
spring跨重定向传递数据
查看>>