JHwong

用户名：dotcpp0724243

访问量：832

签　名：

等　　级
排　　名	3383
经　　验	1946
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

1331: 新三国争霸
浏览：64

第二次训练--D问题（C++解析）
浏览：66

1435: 蓝桥杯历届试题-国王的烦恼
浏览：156

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

奶牛的锻炼

　　作者: JHwong　　　　发表时间：2024-01-11 00:01:28 浏览：122　|　评论：0　

原题链接：奶牛的锻炼

# 奶牛的锻炼
##思路解析
首先，我们可以发现这是一个动态规划问题。因此需要设计一个合理的dp数组来辅助我们完成任务。
大概思路可见代码注释。
##代码实现
```cpp
/* 
 * 题目 1290: 奶牛的锻炼
 * --> we have some status, Like running time, fatigue and running distance
 * because the running distance is what we want to known
 * so the array dp should storage it
 * initialy:
 * dp[run_time][fatigue] = when cow has run run_time minutes and has fatigue, the cow can run the maximum distance.
 * dp[run_time][fatigue] = if run then dp[run_time][fatigue] = dp[run_time - 1][fatigue - 1] + D_i[run_time]
 *                         if rest->run_time + fatigue <= limit then dp[run_time + fatigue][0] = max{dp[run_time + fatigur][0], dp[run_time][fatigue]}
 * maybe we not be able to optimize it
 */
#include<iostream>
#include<cstring>
#define MAX_FATIGUE 505
#define MAX_RUNNING_TIMES 20005

int running_times, fatigue;
int D_i[MAX_RUNNING_TIMES];
int dp[MAX_RUNNING_TIMES][MAX_FATIGUE];

#define max(a, b) ( (a) > (b) ? (a) : (b))
int main() {
  scanf("%d %d", &running_times, &fatigue);
  for (int i = 1; i <= running_times; i++) scanf("%d", D_i + i);
  
  dp[1][0] = 0, dp[1][1] = D_i[1];
  for (int has_running_i_minutes = 1; has_running_i_minutes <= running_times; ++has_running_i_minutes) {
    dp[has_running_i_minutes][0] = dp[has_running_i_minutes - 1][0];
    for (int cur_fatigue = 1; cur_fatigue <= fatigue; ++cur_fatigue) {
      dp[has_running_i_minutes][cur_fatigue] = max(dp[has_running_i_minutes - 1][cur_fatigue - 1] + D_i[has_running_i_minutes],
                                         dp[has_running_i_minutes][cur_fatigue]);
      if (has_running_i_minutes > cur_fatigue) // can rest cur_futigue minutes
        dp[has_running_i_minutes][0] = max(dp[has_running_i_minutes][0], dp[has_running_i_minutes - cur_fatigue][cur_fatigue]);
    }
  }
  printf("%d\n", dp[running_times][0]);
  return 0;
}
```
##dp设计历程
最简单直接的设计方式就是每一个额外的状态都是一个维度，正如代码注释解释的那样。但是问题在于我们能不能继续优化 -- 压缩空间、优化时间。一如我在注释中说的那样似乎不能在优化了。考虑去除fatigue维度，或者说假使其维护值一致是0。也就是说我们把dp[running time]集合压缩为dp[running time]\[0]。此时dp[running time]\[0]就表示一个抽象的概念--集合dp[running time]的最大值。
于是，我们只用考虑这样的压缩是否合法，或者说有利于编码。很快发现dp的转移变成了dp[i] = dp[k] + run_k_minutes，run_k_minutes表示一个区间和值。这是简单想到的，但是问题在于k。因为在i时刻的劳累度0，所以k的范围应该在 0<=k<=i。或者这么说吧，我们还是需要遍历三个维度，定值i,k还要定区间也就是run_k_minutes的值。而区间值可以使用前缀和快速求取，因此求值时间无伤大雅。关在在于区间长度最大不得超过fatigue,事实上这是一个宽松的上界，更为严格的表达是：queue length <= min(fatigue, (i - k)/2)。所以这样带来的代价是虽然空间上压缩似乎是可行的，但是时间上一定会被拖慢。因为遍历的三个维度中两个Time维度，一个fatigue维度。
综上所述，dp[running time]\[fatigue]应该是最优的情况设计，当然欢迎大佬给出更优方案，如果有所新发现。这也是我写下maybe we not be able to optimize it的原因吧。

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-同因查找（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-整数平均值（C++代码）

奶牛的锻炼

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C二级辅导-统计字符（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

1197求助

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （Java代码）

发工资咯（C语言代码）

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-同因查找 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-整数平均值 （C++代码）

奶牛的锻炼

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C二级辅导-统计字符 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

1197求助

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （Java代码）

发工资咯 （C语言代码）

C二级辅导-同因查找（C语言代码）

WU-整数平均值（C++代码）

　　评论区

C二级辅导-统计字符（C语言代码）

发工资咯（C语言代码）