动态规划1234567

Question

题目描述

在一条路上，有 n 棵果树，从左到右编号为 1,2,…,n。小明有 h 个小时的时间，他希望利用这个时间摘到更多的果子。他从 1 出发，向右走（不可往回走），有选择的在一些果树停留一定的时间（是 5 分钟的倍数）摘果子。最后在某一个果树结束摘果子。小明从第 i 个果树到第 i+1 个果树需要走 5*Ti 分钟，在第 i 个果树停留，第一个 5 分钟可以摘到 Fi 个果子，以后每再摘 5 分钟，可以摘到的果子量减少 Di，若减少后的果子量小于 0，则减少后的果子量为 0 。小明想知道自己能获得的最大果子数量.
（提示：贪心 + 优先队列）

输入格式

第一行一个整数 n，表示果树的个数
第二行一个整数 h，表示小明的空闲时间
第三行有 n 个整数，Fi 依次表示每个果树第一个 5 分钟能摘到果子的数量
第四行有 n 个整数，Di 依次表示以后的每 5 分钟摘果子数量比前一个 5 分钟摘果子数量减少的数量
第五行有 n-1 个整数，Ti 表示由第 i 个果树到第 i+1 个果树需要花 5 *Ti 分钟的路程

输出格式

输出只有一行，表示小明最多能摘果子的数量。
数据范围
对于所有数据，2<=n<100,1<=h<=20，1<=Fi<=10^9,0<=Di<=10^9。

样例数据

输入

3
1
4 5 6
1 2 1
1 2

输出

35

备注

样例解释

在第 1 个果树摘 15 分钟，共摘得 4+3+2=9 个果子；
在第 2 个果树摘 10 分钟，共摘得 5+3=8 个果子；
在第 3 个果树摘 20 分钟，共摘得 6+5+4+3=18 个果子；
从第 1 个果树走到第 2 个果树，从第 2 个果树走到第 3 个果树，共用时间 15 分钟。
共得 35 个果子，并且这是最多的数量。

错误的代码：

#include <iostream>
#include <cstring>
#define ll long long

using namespace std;

const int N = 110;
int n, h;
ll F[N], D[N], T[N], f[N][250];

int main()
{
    // 读入
    cin >> n >> h;
    h = h * 60 / 5;
    for(int i = 1; i <= n; i++)
        cin >> F[i];
    for(int i = 1; i <= n; i++)
        cin >> D[i];
    for(int i = 1; i < n; i++)
        cin >> T[i];

    // f[i][j]表示在前 i 个果树摘果子且所用总时间不超过 j 个五分钟的方案摘到的最大果子数
    for(int i = 1; i <= n; i++)
    {
        for(int j = T[i - 1]; j <= h; j++)   // 状态划分根据在第 i 棵果树摘了几个果子
        {
            // 在第 i 个不摘
            f[i][j] = f[i - 1][j - T[i - 1]];    

            // 在第 i 棵果树摘了 k + 1 个
            ll t = 0;
            for(int k = 0; k + 1 <= j - T[i - 1]; k++)
            {
                if(F[i] - k * D[i] > 0) t += F[i] - k * D[i];
                f[i][j] = max(f[i][j], f[i - 1][j - (k + 1) - T[i - 1]] + t);   
            }
        }  
    }

    cout << f[n][h] << endl;

    return 0;
}

请问这段代码错哪了，样例过了，但是WA了。

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7643605
• 除此之外, 这篇博客: C与C++程序设计学习笔记中的 5、汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，每次移动一个圆盘，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘，柱子可以编号为A B C，编程输出n个圆盘从A柱子移动到C柱子的步骤。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  

  解题思路：
  （1）把A柱子上的前N-1个盘子借助C柱子，全部移动到B柱子上（过程暂不考虑），再把第N个盘子由A柱子移动到C柱子上，那么剩下要移动的盘子在B柱子上了。
  （2）把B柱子上的前N-2个盘子借助C柱子，全部移动到A柱子上（过程暂不考虑），再把第N-1个盘子由B柱子移动到C柱子上。
  （3）重复上面的两个步骤即可把A柱子上的盘子全部移动到C柱子上。

  #include <stdio.h>
  void loveyou(int n, char start, char help, char end)
  {
  	if (n >= 2)
  	{
  		loveyou(n - 1, start, end, help);
  		printf("%c------>%c\n", start, end);
  		loveyou(n - 1, help, start, end);
  	}
  	else if (n == 1)
  	{
  		printf("%c------>%c\n", start, end);
  	}
  }
  int main(void)
  {
  	int n = 0;
  	printf("输入圆盘的数量:");
  	scanf("%d", &n);
  	loveyou(n, 'A', 'B', 'C');
  	return 0;
  }
  

  
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^