正文

动态规划习题(一)(2006-7-17 20:26:00)

【收藏】 【评论】 【打印】 【关闭】

标签:ACM 动态规划 最大的和 

题目如下:

最大的和

一天,笨笨带着一道题目找到了你,希望你能帮她解决这道题目:

给你n个数a[1], a[2], ..., a[n](0<n<=16,000, -1,000<=a[i]<=1,000)0<L1<=L2<=n 求长度在[L1,L2]的连续若干个数a[i], a[i+1], ..., a[j], (L1<=j+1-i<=L2) 使得a[i]+a[i+1]+...+a[j]取到最大值, 你只需要输出那个最大值即可。

   

由于n非常大,所以笨笨就算数学再好也无法很好的解决这道题目。这下该看你的了,身为计算机小组的你,应该能轻松搞定这道题目吧。

 

输入文件:

输入文件第一行为三个整数nL1 L2 接下来是用空格或者换行符隔开的n个数, i个数表示a[i]

 

输出文件:

    仅一个数,表示a[i]+a[i+1]+...+a[j]的最大值。

 

Sample Input

5 3 4

3 -1 -2 5 3

 

Sample Output

6

分析:这是一道求最值问题的试题。首先很自然就想到用动态规划思想。于是小弟就试着用这种思想去试试。程序如下:

#include <iostream>
using namespace std;

int N,l1,l2;
int a[16000];
int num[16000];      //当前取最大值时所包含的连续的元素个数
int maxValue[16000]; //第i个元素的最大值

int f(int n)//第n个元素的最大值,即为状态
{
   if (n == 1)
   {
         num[n] = 1;
         return maxValue[n] = a[1];
   }
  
   int max1 = a[n] + f(n-1);  //当前的最大值
  
   if (max1 <= a[n])  //如果比当前值要小,说明最大值为当前值
   {
        num[n] = 1;
        max1 = a[n];             
   }
   else num[n] = ++num[n-1];
  
   //如果连续元素个数比l2要大,则去除多余的元素个数   
   if (num[n] > l2)
   {
       num[n] = l2;
       max1 -= a[n-l2];
   }
   //如果连续元素个数比l1要小,则补足缺少的元素个数
   if (n >= l1 && num[n] < l1)
   {
       for (int i = n-num[n]; i > n-l1+1; i--) 
         max1 += a[i];
       num[n] = l1;
   }
  
   return maxValue[n] = max1;
}

int main()
{
    cin >> N >> l1 >> l2;
   
    for (int i = 1; i <= N; i++)
      cin >> a[i];
     
    f(N);
   
    int maxD = maxValue[l1];
    for (int i = l1; i <= N; i++)
      if (maxD < maxValue[i])maxD = maxValue[i];
    cout << maxD << endl;
   
    system("pause");
    return 0;
}

 

总结:虽然测试了几组数据,还通得过,但不知正确与否。其次,对动态规划的理解不深刻,用了很长的时间才写出来。数学功底不够扎实。不足之处还望高手指点。

阅读(4254) | 评论(3)| 复制链接


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

评论人: 路人 发布时间: 2007-11-20 18:22:00
这种垃圾题都拿出来炫耀 我靠
评论人: csea 发布时间: 2007-8-27 0:10:00
好像是以前转载的 :)
评论人: Alex 发布时间: 2007-8-7 22:14:00
问一下,这是哪里的题目  数据在哪?

发表评论

您的昵称: 昵称不填为“匿名”

您的Email: (可选)

评论内容:(字数请控制在500字以内)