JHwong

用户名：dotcpp0724243

访问量：832

签　名：

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

　　自我简介：

TA的其他文章

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

1427: 蓝桥杯2013年第四届真题-买不到的数目
浏览：39

2529: NOIP2012-同余方程-了解即可
浏览：34

你可能喜欢

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

1301: 尼克的任务

　　作者: JHwong　　　　发表时间：2024-01-11 02:58:18 浏览：92　|　评论：0　

原题链接：尼克的任务

#1301: 尼克的任务
##思路解析
首先可以很明确判断出这是一道线性规划的题目。该题目本人觉得难点在于正反推的问题。所以我会详细解释一下。顺带一提搜索的思路也是可以的，但是这道题状态空间优点大，再加上DFS实现的话应该是会爆时间的（猜测并没有实际验证，hhh）。
接着，考虑如何设计实现代码。很自然可以定义dp数组为时间节点为t时，尼克的最多空闲时间。因此，我们可以快速写出状态转移方程和条件，如下：
> if end_time_of_pre_thing < k < begin_time_of_this_thing then
dp[i] = max{ dp[k] - working_time[i] }

关注到这里的状态转移方程前提条件涉及到前一个状态，也就是前后状态是纠缠的。如果不确定前一个状态，那么后续状态一定是不可知的。因此，我们不可能使用这种状态转移方程进行转移。但是如果采用搜索算法是可以使用的，因为前一个状态可以作为已知条件传入。但是很可惜我排除了搜索算法 -- 我觉得搜索算法大概率会被卡时间而已。
所以，我们必须从别的角度出发解除这种纠缠关系。于是，我们尝试对式子做变换：
> if k < i <= working_time_per_day
dp[k] = max{ dp[i] + free_time }
by the way, if at this moment niko is nothing to do, free time = 1;
else free time = 0

但是为什么是不是+worktime而是freetime。如果加worktime是逆推过程没错，但是成立的情况是已知dp[working time per day] = value。但是我们并不知道。所以只能加freetime因为只能相同性质的东西才能执行+操作。所以，我们给出了另外一个变量freetime,庆幸的是这个状态是可求取的。因此大功告成。因为freetime跟当前时间节点是否空闲有关，所以我们需要统计各个时间节点的事件数量。故此需要how_much_things_at_same_time[]。其次，如果freetime = 0,递推式变为dp[k]=max{dp[k+working_time[things_no]]}。为了方便定位，我们需要排序一下。当然不排序的话就需要邻接表结构来辅助我们了。这个无所谓的。
##代码实现

```cpp
/* 
 * 题目 1301: 尼克的任务
 * the question is a Dynamic Programming Problem.but you can solve the problem by searching all status.
 * we can define the array dp. dp[end time] = when end time,niko have maximum free time.
 * max{ dp[i] } = max{ dp[k] - work_time[i] }, end_time_pre_thing < k < begin_time_of_thing[i],
 * but we can't known the pre_thing,so we should solve the question.
 * max{ dp[k] } =  max { dp[i] + free_time[i] }, k < i <= working_time.
 * if at this moment is free then free_time[i] = 1;
 * else free_time = 0, dp[k] = max{ dp[i] }
 * the answer is dp[1]
 */
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX_NUMBER_OF_THINGS 10005
#define MAX_WORKING_TIME     10005

int dp[MAX_WORKING_TIME];
int working_time, number_of_things;
int how_much_things_at_same_time[MAX_WORKING_TIME];
struct Things
{
  int begin, time;
  friend bool operator < (Things& x, Things&  y)
  {
	return x.begin > y.begin;
  }
}things[MAX_NUMBER_OF_THINGS];

#define min(a, b) ( (a) < (b) ? (a) : (b) )
int main() {
  scanf("%d %d", &working_time, &number_of_things);
  for (int i = 1; i <= number_of_things; ++i) {
	scanf("%d %d", &things[i].begin, &things[i].time);
	how_much_things_at_same_time[things[i].begin] += 1;
  }

std::sort(things + 1, things + number_of_things + 1);
  int point_of_thing = 1;
  for (int now_time = working_time; now_time >= 1; --now_time) {
	if (how_much_things_at_same_time[now_time] == 0)
	  dp[now_time] = dp[now_time + 1] + 1;
	else for (int no_of_thing = 0; no_of_thing < how_much_things_at_same_time[now_time]; ++no_of_thing) 
	  dp[now_time] = std::max(dp[now_time], dp[now_time + things[point_of_thing++].time]);
  }

printf("%d\n", dp[1]);
  return 0;
}
```

0.0分

0 人评分

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

JHwong

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C语言代码）

川哥的吩咐（C语言代码）

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

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

文科生的悲哀（C语言代码）

1301: 尼克的任务

评论区

精彩推荐

回文数字（C语言代码）

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

母牛的故事（C语言代码）

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

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

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

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

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

1224题解

Manchester-汽水瓶问题

JHwong

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C语言代码）

川哥的吩咐 （C语言代码）

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

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

文科生的悲哀 （C语言代码）

1301: 尼克的任务

评论区

精彩推荐

回文数字 （C语言代码）

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

母牛的故事 （C语言代码）

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

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

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

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

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

1224题解

Manchester-汽水瓶问题

C二级辅导-进制转换（C语言代码）

川哥的吩咐（C语言代码）

文科生的悲哀（C语言代码）

　　评论区

回文数字（C语言代码）

母牛的故事（C语言代码）