Problem Description
Now I think you have got an AC in Ignatius.L's"Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence S1, S2, S3, S4 ... Sx, ... Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + ... + Sj (1 ≤ i ≤ j ≤ n).
- Now given an integer m (m> 0), your task is to find m pairs of i and j which make sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx is not allowed).
- But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(ix, jx)(1 ≤ x ≤ m) instead. ^_^
- Input
Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.
Process to the end of file.
Output
Output the maximal summation described above in one line.
- Sample Input
- 1 3 1 2 3
- 2 6 -1 4 -2 3 -2 3
- Sample Output
- 6
- 8
题意: 给你一个序列 n 个数组成, 然后让你在里面找到 m 个字子串(不能有交叉, 也不能有连接 的情况), 让这 m 个子串的和最大.
题解: 一眼扫过去就是 DP, 划分问题, 第 j 个选择或者不选, 选(是继续上一个子串还是重新开一个子串), 不选(不考虑, 所以需要维护一个当前的最大值(ans/tmax))
最初的状态转移方程: d[i][j]=max(d[i][j-1],d[i-1][k])+num[j], 其中 k=i-1,i,...,j-1;(没有优化的话大概三重循环)
数据给的很大, 有两个方面的优化: 时间和空间,
优化: 时间 (选择 k 的那一重循环可以用空间换, 用 pre[i] 来表示到 i 的时候 (不包括 num[i]) 的最大值), 循环的时候更新一下, 就可以不用循环 k 那一层了;
空间: 二维数组优化为一维数组, d[i][j]=max(d[i][j-1], pre[j-1])+num[j], 写出 pre 后明显可以直接去掉一个维度;
优化后的状态转移方程式: d[j]=max(d[j-1],pre[j-1])+num[j]
反思: 这题写的时候, 初始方程可以正常的写出来的, 但是用个 pre 数组来直接去掉 k 的那一层循环是不会的, 思维有点狭隘, 一直就想着通过类似 01 背包的方法来优化, 而没有想到再开一个数组就解决了.
- #include <cstdio>
- #include <iostream>
- #include <cstring>
- using namespace std;
- const int INF=0x3f3f3f3f;
- const int maxn=1e6+5;
- int f[maxn], pre[maxn], a[maxn];
- int main()
- {
- //freopen("in.txt", "r", stdin);
- int m,n;
- while(cin>>m>>n)
- {
- for(int i=1; i<=n; i++)
- cin>>a[i];
- memset(f, 0, sizeof(f));
- memset(pre, 0, sizeof(pre));
- int tmax;
- for(int i=1; i<=m; i++)
- {
- tmax=-INF;
- for(int j=i; j<=n; j++)
- {
- f[j]=max(f[j-1], pre[j-1])+a[j];
- pre[j-1]=tmax; // 注意 pre 的更新的顺序, pre[j-1]被使用后再更新 pre[j-1]
- tmax=max(tmax, f[j]);
- }
- }
- cout<<tmax<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3025165.html