首页 > 代码库 > HDU 1024 最大M字段和

HDU 1024 最大M字段和

2024-09-11 00:35:23   212人阅读

一道关于求最大M字段和的问题，翻译完题之后感觉很简单但就是写不来，后来仿佛推到一个dp式子了，对，仿佛...然后抄袭了个式子，嘿，和我的式子大体相似，然后就是很玄学的优化了...不多瞎bb了

1.首先，定义数组num[n],dp[m][n].
num[n]用来存储n个整数组成的序列.dp[i][j]用来表示由前 j项得到的含i个字段的最大值，且最后一个字段以num[j]项结尾。仔细想想，我们可以知：
dp[i][j]=max(dp[i][j-1]+num[j],dp(i-1,t)+num[j]) (i-1<=t<=j-1.)


2.优化
我们只要找到dp[i][j-1]和dp[i-1][t]的最大值加上num[j]即为dp[i][j].所以，定义一个数组pre_max[n]，用pre_max[j-1]来表示求解dp[i][j]时dp[i-1][t]，得：
dp[i][j]=max(pre_max[j-1],dp[i][j-1])+num[j].


3.再优化
在求解dp[i][j]的同时，我们可以计算出dp[i][t];i<=t<=j的最大值，这个最大值在计算dp[i+1][j+1]的时候需要作为pre_max[j]的形式被使用，我们先把它存在pre_max[n]中。通过时间的节省，我们突然间发现程序执行结束后pre_max[n]的值即为最后的结果，pre_max[n]数组才是我们希望求解的，


4.节省空间
dp[m][n]这个庞大的数组已经不是那么重要了，因此，我们现在用整型数maxx来代替dp[m][n]，用来临时存储dp[i][j]的值，作为求解pre_max[n]的中介。这样就节省了dp[i][j]占用的极大的空间.

技术分享

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 1000005
 6 int pre_max[N],num[N];
 7 int main()
 8 {
 9     int m,n,i,j,maxx;
10     while(~scanf("%d %d",&m,&n))
11     {
12         for(i=1;i<=n;i++)    scanf("%d",&num[i]);  
13         memset(pre_max,0,sizeof(pre_max));    
14         for(i=1;i<=m;++i)
15             {
16                 maxx=0;
17                 for(int k=1;k<=i;++k)   maxx+=num[k];
18                 pre_max[n]=maxx;
19                 
20                 for(j=i+1;j<=n;++j)
21                 {
22                     maxx=max(pre_max[j-1]+num[j],maxx+num[j]);
23                     pre_max[j-1]=pre_max[n];
24                     pre_max[n]=max(maxx,pre_max[n]);
25                 }
26             }
27         printf("%d\n",pre_max[n]);    
28     }
29     return 0;
30 }

 

HDU 1024 最大M字段和


联系
我们