HDU-1024-DP-（滚动数组优化与状态转移）

137 阅读 0 评论 91 点赞

我是靠谱客的博主无聊镜子，这篇文章主要介绍HDU-1024-DP-（滚动数组优化与状态转移），现在分享给大家，希望可以做个参考。

关键是对状态转移的理解。
状态转移方程可以理解为
dp[i][j]=max(dp[i][j-1],dp[i-1][k])+a[j];
j是沿袭上一个串，还是新立一个串（上一个串以k结尾，谁的值最大，谁就是k），取最大值。
当我们发现求dp[i-1][k]时需要一个for时，我们的心情是绝望的。。
并且发现要开的dp数组也很大。。
只能用两个数组来优化，我们发现不用for来求dp[i-1][k]，在计算的时候，可以沿袭上一次的计算，本质是一个 dp[i][j],
的确值得好好看看。
至于这个队列为什么要从i开始，我一开始以为是和优化有关，可是也是很蒙蔽啊，如果是优化的话哪有一个循环就截前面一个数组的。
后来才发现，原来是酱紫。
因为dp[j]在i这个循环里是要更新字段为i时的值得。
而当时在更新之前是 i-1的字段。
我们发现如果一个数的位置小于i，那么他是如何也不能更新在有限的长度内实现 i字段的值的。（只有i能，小于i的元素，就算一个算一个字段，他们也是小于i的，不用更新.并且随着i的增加不能改变的越来越多。！！！！！）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=100001;
int main()
{
//std::ios::sync_with_stdio(false);
int m,n;
int
a[maxn];
while(cin>>m>>n)
{for(int i=1;i<=n;i++)
cin>>a[i];
int dp[maxn];
int
maxx[maxn];
memset(dp,0,sizeof(dp));
memset(maxx,0,sizeof(maxx));
int ans=-2e17;
int all=0;
for(int i=1;i<=m;i++)
{
ans=-2e17;
for(int j=i;j<=n;j++)//对小于i的数来说，新开一个串不会有任何影响，因为小于i，新开的串必然不能以他们开头，
{
dp[j]=max(dp[j-1],maxx[j-1])+a[j];
maxx[j-1]=ans;
if(ans<dp[j])
ans=dp[j];
}
//all=max(all,ans);
}
cout<<ans<<endl;}
return 0;
}