zoj1091 python算法

zoj1091是一道经典的动态规划问题，它的题目描述如下：

有一条直线路，长度为n，起点为0，终点为n。有m个加油站，每个加油站有一个加油量p，和一个位置d，表示在距离起点d的地方可以加p升油。车油箱的容量为c升，每行驶1千米消耗1升油，请问车能否从0到n行驶，如果能，最少需要加几次油？

这道问题可以用动态规划的方法求解。我们可以定义一个一维数组dp，其中dp[i]表示车到达距离i的位置时最少需要加几次油。

那么如何进行状态转移呢？

对于每个加油站，我们可以考虑是否在这个加油站加油。如果不加油，那么dp[i]的值就等于dp[i-1]，因为车没有加油，可以继续往前开。

如果要在这个加油站加油，那么我们需要找到在之前的哪个位置加油次数最少。假设这个加油站的位置是j，加油量是p，那么我们需要在距离j-p的位置加油，这样才能到达加油站j。那么在距离j-p的位置加油的次数就是dp[j-p]，加上这个加油站的加油次数1，就是dp[j-p]+1。我们还需要判断车的油箱容量是否够用，如果不够用，那么就不能在这个加油站加油。我们可以用一个变量tank来记录油箱中的油量，每经过一个位置就减去1，如果遇到加油站就加上p。

最后，dp[n]就是最终的答案，表示车到达终点n时最少需要加几次油。

下面是使用Python实现这道题的代码：

相关问题

ZOJ 1188python

ZOJ 1188是一个题目的编号，它对应的题目是"Python的简单应用"。这个题目要求你编写一个Python程序，实现一个简单的功能。

具体来说，题目要求你编写一个程序，读入一个整数n，然后输出n个"*"字符。例如，如果输入为3，则输出为"***"。

以下是一个可能的解答示例：

n = int(input())
print("*" * n)

这个程序首先读入一个整数n，然后使用乘法操作符将"*"字符重复n次，并将结果打印出来。

zoj 2212python

这是一道ZOJ Online Judge上的题目，题目名称为“Work Reduction”。

题目描述：

有n个工人，m个任务，每个工人可以完成一些任务，任务可以被多个工人完成。每个工人有一个效率，表示他完成一个任务所需的时间。每个任务有一个固定的利润。任务可以分成若干个子任务，每个子任务可以被不同的工人完成，子任务完成时间等于完成该子任务的工人的效率之和。现在要求你将所有任务完成，最小化完成时间的和，即最小化 Σ(任务完成时间*任务利润)。

输入格式：

第一行两个正整数n,m，表示工人数和任务数。 接下来的m行，每行包含若干个正整数，表示该任务可以被哪些工人完成。每个正整数表示一个工人的编号，负数表示该任务的一个子任务需要完成，编号为对应正整数的工人的效率为完成该子任务的时间。

输出格式：

输出一个整数，表示最小化任务完成时间的和。

样例输入：

3 3
1 -1 -2
1 -2
2 -1

样例输出：

7

提示：

1<=n<=200，1<=m<=200，每个工人效率<=1000，每个任务利润<=10000。