hdu 1024 HDU 1024 Max Sum Plus Plus(ダイナミックプランニングは詳細)
3623 ワード
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.
长い间考えていましたが、解决して1日置いて、今日やっと义无反顾にブログをやりました!!
昨日ルームメイトBRと4時ごろまで話していたので、休みになっても早く帰らなければならないようです(寮に落ちないように)
本題に戻って、そんなに長い間詰まっていて、DPは独立して考えています.
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.
长い间考えていましたが、解决して1日置いて、今日やっと义无反顾にブログをやりました!!
昨日ルームメイトBRと4時ごろまで話していたので、休みになっても早く帰らなければならないようです(寮に落ちないように)
本題に戻って、そんなに長い間詰まっていて、DPは独立して考えています.
#include//1000ms 984ms ^^ ( ， )
#include
#include
using namespace std;
int dp[1222222],alone[1222222],a[1222222];
int main()
{
int i,j,n,m;
while(~scanf("%d",&m))
{
scanf("%d",&n);
memset(dp,0,sizeof(dp));
memset(alone ,0,sizeof(alone));
for(i=1;i<=n;i++)scanf("%d",&a[i]);
int tmax;
//★ i alone[j]: j ( j) i ★
for(i=1;i<=m;i++)//★ i
{
tmax=-(1<<30);
//printf("a[],alo[],dp[]
");
for(j=i;j<=n;j++)// i : i , i i
{
dp[j]=_cpp_max(dp[j-1],alone[j-1])+a[j];
/*★★dp a[j] a[j-1] 。al a[j] i
★ i alone[j]: j ( j) i ★ alone[j-1]+a[j]
alone j , i "j "//*///\
printf("%2d %2d %2d
",a[j],alone[j-1],dp[j]);
if(j>i)alone[j-1]=tmax;
//★ i alone[j]: j ( j) i ( ( n ) tmax)★//\
alone i j-1 i-1 j-1 ， j-1 i .//\
alone[n-1],reason: i , ★i-1 alone[i-1 n-1]( ( a[n]) tmax)//\
n-1 , 1 j=n-1, n-2 n-2 ( ( m ) tmax)
if(tmax
/*
★( ， ...... + -- !)
， ， （m 6 ）
2 6
-1 4 -2 3 -2 3
4 3,-2,3 or 4,-2,3+3=8
*/