hdu1003: Max Sum

布满荆棘的人生 2022-07-14 09:22 144阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=1003][http_acm.hdu.edu.cn_showproblem.php_pid_1003]

# 定位 #

*  经典动态规划

# 分析 #

*  题目原形为最大子序列之和问题
 *  本题中增加了处理始止位置的要求，未增加难度，加大了审题和调试的工作量。
 *  递推关系式  
    
    
    dp\[i\]=max(dp\[i−1\],dp\[i−1\]\+a\[i\])

# 代码 #

*  基本版：只求最大子序列的和，不求始止位置

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int T,t,num,i;
        int max;
        int a[100001] = {
       0};
        int dp[100001] = {
       0};
    
        scanf("%d*c",&T);
        t = 1;
    
        while(T--)
        {
            scanf("%d*c",&num);
            memset(a,0,sizeof(a));
            memset(dp,0,sizeof(dp));
    
            scanf("%d*c",&a[0]);
            max = dp[0] = a[0];
            for(i=1;i<num;i++)
            {
                scanf("%d*c",&a[i]);
                dp[i] = dp[i-1] + a[i] > a[i] ? dp[i-1] + a[i] : a[i];
                max = max > dp[i] ? max : dp[i];
            }
            printf("Case %d:\n%d",t++,max);
            printf("\n");
        }
        return 0;
    }

*  基本版内存优化

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int T,t,num,i;
        int max;
        int dp = 0;
        int a = 0;
    
        scanf("%d*c",&T);
        t = 1;
    
        while(T--)
        {
            scanf("%d*c",&num);
            scanf("%d*c",&a);
            max = dp = a;
            for(i=1;i<num;i++)
            {
                scanf("%d*c",&a);
                dp = dp > 0 ? dp + a : a;
                max = max > dp ? max : dp;
            }
            printf("Case %d:\n%d",t++,max);
            printf("\n");
        }
        return 0;
    }

*  本题

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int T,t,num,i;
        int pos_st,pos_en,max;
        int a[100001] = {
       0};
        int dp[100001] = {
       0};
    
        scanf("%d*c",&T);
        t = 1;
    
        while(T--)
        {
            scanf("%d*c",&num);
            memset(a,0,sizeof(a));
            memset(dp,0,sizeof(dp));
    
            scanf("%d*c",&a[0]);
            max = dp[0] = a[0];
            pos_en = 0;
            for(i=1;i<num;i++)
            {
                scanf("%d*c",&a[i]);
                dp[i] = dp[i-1] + a[i] > a[i] ? dp[i-1] + a[i] : a[i];
                if(max <= dp[i])
                {
                    max = dp[i];
                    pos_en = i;
                }
            }
            pos_st = pos_en;
            for(i=pos_en;i>=0;i--)
            {
                max -= a[i];
                if(max == 0)
                {
                    pos_st = i;
                }
            }
            printf("Case %d:\n%d %d %d\n",t++,dp[pos_en],pos_st+1,pos_en+1);
            if(T != 0)
            {
                printf("\n");
            }
        }
        return 0;
    }

# 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">46MS</td> 
   <td align="center">2192K</td> 
   <td align="center">1026 B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

*  解题过程中，遇到了格式错误(Presentation Error)问题。  
    格式错误，应立即重新审题，判断正确格式，切忌盲目修改。  
    出现一处格式错误，OJ判题结果为PE；多处格式错误，结果就变成WA了。 连续PE会给自信心带来极大挑战。

Thank you

[http_acm.hdu.edu.cn_showproblem.php_pid_1003]: http://acm.hdu.edu.cn/showproblem.php?pid=1003