> 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;
> }

• Re:谁说这个程序是标程？！！！ (52) simple85 2008-08-21 00:46:29