跪求一个证明我错了的用例……

Wayne posted @ Fri, 25 Jan 2013 14:29:43 +0000 in Experience , 4008 readers

这两天无聊刷HDOJ,各种不爽啊。C语言果然是忘记光了。

今天遭遇1003题。这题网上一搜倒是一堆讨论的,全是不知道自己死在哪的。而回复则大多是“这是一道典型/经典/简单的动态规划题”,然后给个AC的代码。我不知道动态规划是什么,当年学的时候没注意听就算听了现在也早忘记掉了,但是你给个正确的代码并不能表示我的就是错的啊…… 如果说错了,那么到底错哪里呢…… 跪求一个能证明我错了的测试用例……

HDOJ 1003 题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1003

我的代码:

 

#include <stdio.h>

int main(){
    int times, numbers;
    long a, result, pretend;
    int i,j,s,e;

    scanf("%d",&times);
    for(i=1;i<=times;i++){
        scanf("%d",&numbers);
        scanf("%ld",&a);
        result = a; 
        pretend = a; 
        s = 1; 
        e = 1; 
        for(j=2;j<=numbers;j++){
            scanf("%ld",&a);
            pretend += a; 
            if(pretend>result){
                result = pretend;
                e = j; 
            }  
            if(a>result){
                result = a; 
                s = j; 
                e = j; 
            }  
        }  
        printf("Case %d:\n%ld %d %d\n",i,result,s,e);
        if(i!=times){
            printf("\n");
        }  
    }  
    return 0; 
}

 

----- 2013.02.01 P.S.-------------------

因为不知道DP具体是个啥,今天抽空查了些资料,草草研究了下DP究竟是怎么回事,并参考了别人的一些代码,虽然错误用例还是没能找到。 我的代码的算法大致可以这样描述吧:

          MaxSum[1] = ValueN[1];

          MaxSum[n] = (MaxSum[n-1]+ValueN[n]>MaxSum[n-1]? MaxSum[n-1]+ValueN[n]: MaxSum[n-1]) > ValueN[n] ? $1: ValueN[n]

$1 表示 前一个判断得到的结果。

第一个判断 MaxSum[n-1] + ValueN[n] > MaxSum[n-1] ?  只要 ValueN[n] >0就能成立

第二个判断 MaxSum[n-1] + ValueN[n] > ValueN[n],成立条件是 MaxSum[n-1] > 0,第二个判断的另一个分支 MaxSum[n-1] > ValueN[n] 则不能直接看出正负关系,但是因为要走到这个分支,必然要求ValueN[n]为负,要小于一个负数的话,MaxSum[n-1] 必然也得是负数,这样才能让条件不成立从而得到ValueN[n]。换句话说,只要 MaxSum[n-1] >0, 第二个判断得到的结果都是 MaxSum[n-1] + ValueN[n] 或者 MaxSum[n-1]。

写成这样了之后,看上去好像也是个DP吧…… 不知道有没有高人能给分析分析。

   

Avatar_small
scturtle said:
Sat, 26 Jan 2013 02:13:12 +0000

"If there are more than one result, output the **first** one."
if(a>result)

Avatar_small
Wayne said:
Sat, 26 Jan 2013 11:58:36 +0000

那这个“first" 到底怎么定义呢? 比如说一个数列是 0 0 1 0 0 ,那么输出应该是 1 1 5 还是 1 1 3 还是1 3 3?

实际上我把 a>=result 改成 a>result 也是一样WA的,把上面的pretend >= result 改成 > 也还是一样WA

Avatar_small
夏福的猎鹿帽 said:
Mon, 28 Jan 2013 11:04:37 +0000

你这个代码没用到dp吧,这个用O(n)复杂度即可解决。而且我不太看得懂你的代码,
scanf("%d",×);
for(i=1;i<=times;i++){
你times赋初值了吗

Avatar_small
Wayne said:
Mon, 28 Jan 2013 15:55:08 +0000

我的是没用到dp,但是我的也没比O(n)更复杂…… scanf("%d",×); 这里其实是 scanf("%d",&times); 复制到这里的时候不知道为什么被改了汗…… 我这就改回去……

夏福的猎鹿帽 said:
Tue, 29 Jan 2013 05:55:18 +0000

7 0 6 -1 1 -6 7 -5
这个例子你就通不过啊,你的输出是
7 6 6

Avatar_small
Wayne said:
Tue, 29 Jan 2013 08:10:17 +0000

额,这个不应该是 7 6 6 吗? 或者说应该是 7 1 6? 我不明白这里的 first 怎么认定。我可以把程序改成能得到 7 1 6的,但是一样WA……

Avatar_small
shicker said:
Fri, 01 Feb 2013 01:47:29 +0000

7 0 6 -1 1 -6 7 -5
这个答案不应该是 14 0 6 么? 如果first是0的话。

题目给出的sample是错的吧

Avatar_small
Wayne said:
Fri, 01 Feb 2013 03:04:57 +0000

不是的。第一个数字7表示这一个数列总共有7个数字,不算在数列本身内。而数列的起止位置是从传统的1开始算,不是计算机的0开始

Avatar_small
たのしそう said:
Thu, 28 Feb 2013 01:39:51 +0000

不明觉厉~这道题解法很多,不过不管怎么做核心算法都不会超过5行。


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter