posts - 99,  comments - 8,  trackbacks - 0
hdu 1087 DP
//本题是在 grids 2757的基础上得到解决的，即找到最大子例的和
// sum[i]   用于存放到 i 位置为止的子序列的和,所以只需要找到前i - 1 中的sum 所存的最大值再加上本身就可以了

#include <stdio.h>
#include <stdlib.h>

int main ()
{
    int b[1001];
    int n;
    __int64 sum[1001];  //用于存放到 i 位置为止 的子序列的和 
    
    while (scanf ("%d", &n) && n)
    {
          
          for ( int i = 0; i < n;i ++)
          {
              scanf ("%d", &b[i]);
          }
          
          sum[0] = b[0];   
          for (int i = 1; i < n; i ++)               //下面的处理和 grids      2757的处理思想是一样的，只不过sum  数组存的是和值
          {
              int tempMaxsum = 0;
              for (int j = 0; j < i; j ++)     //因为 i 之前的和值已经存储在了sum中，
                                               // 所以只需要找到最大的tempMaxSum后再加上 i 位置本身的值就可以了 
              {
                  if (b[j] <b[i] && tempMaxsum < sum[j])
                  {
                           tempMaxsum = sum[j];   
                  }
              }
              
              sum[i] = tempMaxsum + b[i];
              
          }
          
          __int64 max = -1;
          for (int i = 0; i < n; i ++)
          {
              if (max < sum[i])
              {
                      max = sum[i];
              }
              
          } 
          printf ("%I64d\n",max);
          
    }
    
    return 0;
}
posted on 2010-08-14 21:35 雪黛依梦 阅读(759) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2024年4月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜