HDU 1024 Max Sum Plus Plus(動的に計画して、1つの配列を与えて、それを求めてm個の交差しないサブセグメントと最大値の問題に分けます)...
8804 ワード
Max Sum Plus Plus
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6725 Accepted Submission(s): 2251
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 S
1, S
2, S
3, S
4 ... S
x, ... S
n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S
x ≤ 32767). We define a function sum(i, j) = S
i + ... + S
j (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(i
1, j
1) + sum(i
2, j
2) + sum(i
3, j
3) + ... + sum(i
m, j
m) maximal (i
x ≤ i
y ≤ j
x or i
x ≤ j
y ≤ j
x 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(i
x, j
x)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S
1, S
2, S
3 ... S
n.
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
Hint
Huge input, scanf and dynamic programming is recommended.
Author
JGShining
本題の大まかな意味は1つの配列を与えて,m個の交差しないサブセグメントと最大値に分ける問題を求めることである.
Numを所与の配列とし、nを配列中の要素総数とし、Status[i][j]は前のi個の数がi番目の数を選択した上でjセグメントに分割された最大値を表し、そのうち1<=j<=i<=n && j<=m、状態遷移方程式は:
Status[i][j]=Max(Status[i-1][j]+Num[i],Max(Status[0][j-1]~Status[i-1][j-1])+Num[i])
一見、この方程式は驚くべきことに、問題のnの制限範囲は1~1000000であり、mの制限範囲は与えられていないため、mは少し大きくなるとメモリが爆発する.しかし、よく分析すると、Status[i][j]の解はStatus[*][j]とStatus[*][j-1]にしか関係していないため、本題は2つの1次元配列で状態遷移を完了することができる.
さらに分析すると、Max(Status[0][j-1]~Status[i-1][j-1])は単独で求める必要はないことがわかります.now_を求めてStatus(今回の状態の配列を保存)中にpre_Status(前回の状態を保存した配列)で同期更新を行います.
状態dp[i][j]
前のj個の数、iグループを構成する和の最大値があります.
意思決定:j番目の数は、i番目のグループに含まれるか、それとも自分で独立してグループ化されるか.
方程式dp[i][j]=Max(dp[i][j-1]+a[j],max(dp[i-1][k])+a[j])0
空間複雑度,m未知,n<=1000000, 配列をスクロールし続けます.
時間複雑度n^3.n<=10000000. 明らかにタイムアウトし、最適化を継続します.
max(dp[i-1][k])は、前のグループ0.....j-1の最大値である.dp[i][j]を計算するたびに前のj個を記録することができる.
の最大値を配列で保存 次に計算するときに使えますが、時間の複雑さはn^2です.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6725 Accepted Submission(s): 2251
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 S
1, S
2, S
3, S
4 ... S
x, ... S
n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S
x ≤ 32767). We define a function sum(i, j) = S
i + ... + S
j (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(i
1, j
1) + sum(i
2, j
2) + sum(i
3, j
3) + ... + sum(i
m, j
m) maximal (i
x ≤ i
y ≤ j
x or i
x ≤ j
y ≤ j
x 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(i
x, j
x)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S
1, S
2, S
3 ... S
n.
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
Hint
Huge input, scanf and dynamic programming is recommended.
Author
JGShining
本題の大まかな意味は1つの配列を与えて,m個の交差しないサブセグメントと最大値に分ける問題を求めることである.
Numを所与の配列とし、nを配列中の要素総数とし、Status[i][j]は前のi個の数がi番目の数を選択した上でjセグメントに分割された最大値を表し、そのうち1<=j<=i<=n && j<=m、状態遷移方程式は:
Status[i][j]=Max(Status[i-1][j]+Num[i],Max(Status[0][j-1]~Status[i-1][j-1])+Num[i])
一見、この方程式は驚くべきことに、問題のnの制限範囲は1~1000000であり、mの制限範囲は与えられていないため、mは少し大きくなるとメモリが爆発する.しかし、よく分析すると、Status[i][j]の解はStatus[*][j]とStatus[*][j-1]にしか関係していないため、本題は2つの1次元配列で状態遷移を完了することができる.
さらに分析すると、Max(Status[0][j-1]~Status[i-1][j-1])は単独で求める必要はないことがわかります.now_を求めてStatus(今回の状態の配列を保存)中にpre_Status(前回の状態を保存した配列)で同期更新を行います.
状態dp[i][j]
前のj個の数、iグループを構成する和の最大値があります.
意思決定:j番目の数は、i番目のグループに含まれるか、それとも自分で独立してグループ化されるか.
方程式dp[i][j]=Max(dp[i][j-1]+a[j],max(dp[i-1][k])+a[j])0
空間複雑度,m未知,n<=1000000, 配列をスクロールし続けます.
時間複雑度n^3.n<=10000000. 明らかにタイムアウトし、最適化を継続します.
max(dp[i-1][k])は、前のグループ0.....j-1の最大値である.dp[i][j]を計算するたびに前のj個を記録することができる.
の最大値を配列で保存 次に計算するときに使えますが、時間の複雑さはn^2です.
/*
dp[i][j] j ， i 。 ：
j ， i ， 。
dp[i][j]=Max(dp[i][j-1]+a[j] , max( dp[i-1][k] ) + a[j] ) 0 ，m ，n<=1000000， 。
n^3. n<=1000000. ， 。
max( dp[i-1][k] ) 0....j-1 。
dp[i][j] j
， n^2.
*/
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN 1000000
#define INF 0x7fffffff
int dp[MAXN+10];
int mmax[MAXN+10];
int a[MAXN+10];
int main()
{
int n,m;
int i,j,mmmax;
while(scanf("%d%d",&m,&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
mmax[i]=0;
dp[i]=0;
}
dp[0]=0;
mmax[0]=0;
for(i=1;i<=m;i++)
{
mmmax=-INF;
for(j=i;j<=n;j++)
{
dp[j]=max(dp[j-1]+a[j],mmax[j-1]+a[j]);
mmax[j-1]=mmmax;
mmmax=max(mmmax,dp[j]);
}
}
printf("%d
",mmmax);
}
return 0;
}