Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:谁说这个程序是标程?!!!

Posted by MasterLuo at 2008-08-21 00:37:09 on Problem 2593
In Reply To:貌似数据有问题 Posted by:simple85 at 2008-08-21 00:16:30
> 6
> 3 3 -3 4 -2 1
> 看看这组数据,正确结果是10
> 可有些标程中是11
> 而且我用结果是11的标程提交是正确的
> 我说的就是这个标程:
> 
> POJ 2593(动态规划)
> 题目来源 :PKU 2593
> 
> 解法类型 :动态规划应用
> 
> 作    者 :刘亚宁
> http://acm.pku.edu.cn/JudgeOnline/problem?id=2593
> 
> 题目大意:
>         抽取一个整数序列的两个子序列,求所有抽取方法中得到两个序列和的最大值。
> 
> 题目思路:
>         用两个数组数组记录从前和从后子序列加和的最大值,每个元素的值为从前(后)加和至该位置得到的最大值。
>         遍历数组每个位置,找出所有位置为分界点的最大值即为结果。
>         其中得到子序列最大和过程比较特殊,详见代码。
> 
> 提交情况:
>         Run time error(以后简称rte)一次:数组不够大,省题没注意数据范围。
>         Time Limit Exceeded(以后简称tle)一次:没有应用前和后的数组进行数据的存储。
> 
> 注意:
>         两个子序列和的最大值 不是最大子序列和 与 第二大不想交子序列和 的sum(错因:例如数据3 3 -3 4 -2 1)
> 
> 源程序:  
> 代码:
> #include <iostream>
> #define MIN -2000000000
> using namespace std;
> 
> long a[110000],front[110000],back[110000];
> 
> int main()
> {
>         long num,i,r,k;
>         while(cin>>num,num)
>         {
>                 for(i=1;i<=num;i++) cin>>a[i];
>                 front[0]=MIN;//特殊处理边界情况
>                 back[num+1]=MIN;
>                 for(i=1;i<=num;i++)
>                 {
>                         k=(front[i-1]+a[i])>a[i]?(front[i-1]+a[i]):a[i];
>                         front[i]=front[i-1]>k?front[i-1]:k;//从前向后,找到加上a对应位置的值、不加该值、和只有该值(可能是一序列的开头)的最大者,记录于front数组
>                 }
>                 for(i=num;i>=1;i--)
>                 {
>                         k=(back[i+1]+a[i])>a[i]?(back[i+1]+a[i]):a[i];
>                         back[i]=back[i+1]>k?back[i+1]:k;
>                 }//从后向前,进行类似的活动
>                 r=MIN;
>                 for(i=1;i<num;i++)
>                         if(front[i]+back[i+1]>r) r=front[i]+back[i+1];//从 所有前后两个序列的分界位置 所对应的和中 找到最大的 即为结果
>                 cout<<r<<endl;
>         }
>         return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator