关于最大连续子序列问题,我以前学DP的时候做过(Max Sum HDU1003)这道题,不过那时候只是草草的学了下,代码还是参考别人的,不懂原理,昨天在CF上做到类似的题目,然后跪了几把,决定把这类题目重新做了下(其实也就只是做了3道题目)
首先 : 关于求一段整数序列的最大连续子序列的话,有好几种方法,最容易想到的就是O(N^2)暴力枚举每一个start 和end点,不过,一般会超时,另外还有分治的方法,复杂度在O(n*logn),不过我没敲过(囧)、好吧,我昨天终于弄懂了那种O(n)的算法:因为最大的那一段肯定是以1~n中 的某一个点结束的,所以枚举他(枚举每一个end点),然后当枚举第k个点的时候,判断前前面累加的和sum是否大于0,是则加上a[k],不是的话sum = a[k],然后就OK了。
HDU 1231 (该题还需要求开始和结束的位置)
int sum = -1; int ans = 0; int l = 0, r = 0; int L = 0 , R = 0; for (int i=1;i<=N;i++) { if (sum < 0) { sum = aa[i]; l = aa[i]; r = aa[i]; } else { sum += aa[i]; r = aa[i]; } if (sum > ans) { ans = sum; R = r; L = l; } } printf("%d %d %d\n",ans,L,R);
然后么,是上次在POJ上碰到过的一道题目 POJ - 2593
题意 : 求两段不想交的子序列和最大。
我的想法是在求出某一点k,[1,k](保存在Left数组中)中最大的,和(k,n](保存在Right数组中)中最大,然后用扫一遍就可以获得答案了,在求Left和Right数组的时候可以递推过去的。
总复杂度O(n)
for (int i=1;i<=N;i++) scanf("%d",&aa[i]); int sum; int rr , ll; sum = Left[1] = aa[1]; for (int i=2;i<=N;i++) { if (sum <= 0) { sum = aa[i]; } else { sum += aa[i]; } Left[i] = max(Left[i-1],sum); } sum = Right[N] = -INF; for (int i=N;i>=2;i--) { if (sum <= 0) { sum = aa[i]; } else { sum += aa[i]; } Right[i-1] = max(Right[i],sum); } int ans = -INF; for (int i=1;i<N;i++) ans = max(ans,Left[i]+Right[i]); printf("%d\n",ans);
最后一道题目是,HDU上的1024
题意 : 从两段扩展到了m段
PS : 第一眼看到感觉够NB的。
思路 : 采用DP的方法,用一个数组dp[i][j]保存i段的情况下,以a[j]结尾的最优解。
状态转移方程为 : dp[i][j]=max{dp[i][j-1]+a[j],dp[i-1][k]+a[j],(i-1<=k<j)} (i<=j<=n-m+i) PS : 其实和一段的一样,只要考虑a[j]是附加到前一段还是单个成为一段即可。
dp数组在使用的时候可以只开一个dp[2][maxn]来操作,
bool flag = 1; for (int i=1;i<=n;i++) { dp[0][i] = dp[1][i] = 0; scanf("%I64d",&a[i]); } for (int i=1;i<=m;i++) { dp[flag][i] = dp[1-flag][i-1] + a[i]; LL max_n = dp[1-flag][i-1]; for (int j=i+1;j<=n-m+i;j++) { max_n = Max(max_n,dp[1-flag][j-1]); dp[flag][j] = Max(dp[flag][j-1],max_n)+a[j]; } flag = 1 - flag; } flag = 1 - flag; LL ans = -((LL)1 << 55); for (int i=m;i<=n;i++) ans = Max(ans,dp[flag][i]); printf("%I64d\n",ans);
不过这道题目似乎有点水,因为如果m很大的话乘上n(100W)的话,复杂度肯定要爆的。
所以暂时就这样,如果下次有更加高效的方法的话再来更新本文。