正文

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

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/argol/16648.html

分享到:

题目如下: 最大的和 一天,笨笨带着一道题目找到了你,希望你能帮她解决这道题目: 给你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非常大,所以笨笨就算数学再好也无法很好的解决这道题目。这下该看你的了,身为计算机小组的你,应该能轻松搞定这道题目吧。   输入文件: 输入文件第一行为三个整数n,L1, 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;}   总结:虽然测试了几组数据,还通得过,但不知正确与否。其次,对动态规划的理解不深刻,用了很长的时间才写出来。数学功底不够扎实。不足之处还望高手指点。

阅读(7936) | 评论(3)


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

评论

loading...
您需要登录后才能评论,请 登录 或者 注册