首页 > ACM题库 > HDU-杭电 > Hdu 1858 Max Partial Value I-动态规划[解题报告] C++
2013
12-23

Hdu 1858 Max Partial Value I-动态规划[解题报告] C++

Max Partial Value I

问题描述 :

HenryFour has a number of stones which have different values from -4444 to 4444. He puts N stones in a line and wants to find the max partial value of these N stones.

Assume the values of the N stones in line are: v1, v2, v3, v4, …, vN. The partial vaule of stones from Lth stone to Rth stone (1 ≤ L ≤ R ≤ N) is the sum of all the stones between them. i.e. PartialV(L, R) = v[L] + v[L+1] + …. + v[R] (1 ≤ L ≤ R ≤ N)

Since the number of stones (N) is very very large, it is quite difficult for HenryFour to find the max partial value. So could you develop a programme to find out the answer for him?

输入:

There are several test cases in the input data. The first line contains a positive integer T (1 ≤ T ≤ 14), specifying the number ot test cases. Then there are T lines. Each of these T lines contains a positive number N followed by N integers which indicate the values of the N stones in line.
1 ≤ N ≤ 1,000,000
-4444 ≤ v[i] ≤ 4444

输出:

Your program is to write to standard output. For each test case, print one line with three numbers seperated by one blank: P L R. P is the max partial value of the N stones in line. L and R indicate the position of the partial stones. If there are several Ls and Rs that have the same value PartialV(Li, Ri) = P, please output the minimum pair. For pair (Li, Ri) and (Lj, Rj), we define (Li, Ri) < (Lj, Rj) if and only if: Li < Lj or (Li == Lj and Ri < Rj)

样例输入:

3
4 32 -39 -30 -28
8 1 2 3 -10 1 -1 5 1
10 14 -12 -8 -13 3 5 42 -24 -32 -12

样例输出:

32 1 1
6 1 3
50 5 7

Hint
Huge input and output,scanf and printf are recommended.

#include<stdio.h>
#define inf 0x7fffffff
struct node
{
int l;
int r;
__int64 w;
}p[1000000];
__int64 a[1000000];
int main()
{
int t,i,k,n;
scanf("%d",&t);
  while(t--)
  {
    scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
scanf("%I64d",&a[i]);
p[i].w=a[i];
p[i].l=p[i].r=i;
 }
    p[0].w=0;
   p[0].l=1;
    __int64 max=-inf;
    for(i=1;i<=n;i++)
{
  if(p[i].w<=p[i-1].w+a[i])
  {
p[i].w=p[i-1].w+a[i];
p[i].l=p[i-1].l;

  }
 if(p[i].w>max)
 {
max=p[i].w;
k=i;
 }
}
  printf("%I64d %d %d\n",max,p[k].l,p[k].r);


  }
}

 


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), niwenxianq@qq.com
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.