HDU - 1024 DP
发布日期:2021-09-07 21:17:19 浏览次数:2 分类:技术文章

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

题目大意:

  • 给你n个数,让你从中找m个连续且互不相交的区间,然后使得所有区间元素和最大。

数据范围:

1n106,32768ai32767m>01≤n≤106,−32768≤ai≤32767,m>0

解题思路:

首先确定一个状态,dp[i][j]代表前j个数组成i组的最大值,状态转移方程即为:

dp[i][j]=max(dp[i][j1],max(dp[i1][k]))+a[j](1k<j)dp[i][j]=max(dp[i][j−1],max(dp[i−1][k]))+a[j](1≤k<j)
其中前部分为将第j个加入第i-1段,后部分为第i段以第j个元素开始。但是这个题有点让人难受的是他的m不告诉你具体范围,不过这个题只能用
O(nm)O(n∗m)的复杂度做,由状态转移方程dp[i][j]可以由dp[i][j-1]转移过来,那就只和上一个状态有关,所以就可以用一维数组代替,即为
dp[j]=max(dp[j1],Max[j])+a[j](Max[j]dp[k](1k<j))dp[j]=max(dp[j−1],Max[j])+a[j](其中Max[j]代表dp[k](1≤k<j)的最大值)
再用Maxm记录分成m段时的最大值,即为最后答案。

AC代码:

#include
#include
#include
#include
#include
using namespace std;typedef long long LL;const LL INF = 1LL << 50;const int maxn = 1e6;LL Max[maxn + 5];LL dp[maxn + 5];LL a[maxn + 5];LL Maxm;int n, m;int main() { while(scanf("%d%d", &m, &n) != EOF) { for(int i = 1; i <= n; i++)scanf("%lld", &a[i]); memset(dp, 0, sizeof(dp)); memset(Max, 0, sizeof(Max)); for(int i = 1; i <= m; i++) { Maxm = -INF;//Maxm每次初始化为-oo for(int j = i; j <= n; j++) { dp[j] = max(dp[j - 1], Max[j]) + a[j]; Max[j] = Maxm;//Max[j]记录上一状态前j-1个的最大值。 Maxm = max(Maxm, dp[j]); } } printf("%lld\n", Maxm); } return 0;}

转载于:https://www.cnblogs.com/TRDD/p/9813536.html

转载地址:https://blog.csdn.net/weixin_34304013/article/details/94568446 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:mybatis 找不到映射器xml文件 (idea)
下一篇:再次用CodeIgniter实现简易blog

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年03月01日 18时51分50秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章