JHwong

用户名：dotcpp0724243

访问量：537

签　名：

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

　　自我简介：

TA的其他文章

蓝桥第7/8届练习题解
浏览：72

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

奶牛的锻炼

　　作者: JHwong　　　　发表时间：2024-01-11 00:01:28 浏览：106　|　评论：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的其他文章

你可能喜欢

不容易系列2 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

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

点我有惊喜！你懂得！

奶牛的锻炼

评论区

精彩推荐

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

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

printf基础练习2 （C语言代码）

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

淘淘的名单（C语言代码）

【简单计算】（C语言代码）

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

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

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

字符逆序（C语言代码）

JHwong

TA的其他文章

你可能喜欢

不容易系列2 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

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

点我有惊喜！你懂得！

奶牛的锻炼

评论区

精彩推荐

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

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

printf基础练习2 （C语言代码）

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

淘淘的名单 （C语言代码）

【简单计算】 （C语言代码）

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

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

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

字符逆序 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

　　评论区

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

淘淘的名单（C语言代码）

【简单计算】（C语言代码）

字符逆序（C语言代码）