p1004 [noip2000 提高组] 方格取数

题目描述

给定一个 $n\times m$ 的矩阵，矩阵中的每个数都是非负整数。从矩阵的左上角走到右下角，每次只能向右或向下走一步，沿途经过的数都要累加起来。请问，求出一条从左上角走到右下角的路径，使得路径经过的数之和最小，输出这个最小值。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示矩阵的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个非负整数，表示矩阵中的一个数。

输出格式

输出一个整数，表示从左上角走到右下角的最小路径和。

数据范围

$1\le n,m\le 200$，矩阵中的数均为非负整数且不超过 $100$。

输入样例

3 3
1 3 5
2 1 3
2 2 1

输出样例

8

算法1

(动态规划) $O(nm)$

状态表示：$f[i][j]$ 表示从 $(1,1)$ 走到 $(i,j)$ 的最小路径和。

状态转移：

- $f[i][j]=\min(f[i-1][j],f[i][j-1])+a[i][j]$

时间复杂度

参考文献

python3 代码

C++ 代码

java 代码

算法2

(暴力枚举) $O(nm2^{n+m})$

blablabla

时间复杂度

参考文献

C++ 代码

相关问题

p1025 [noip2001 提高组] 数的划分

题目描述

将正整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5；

1，5，1；

5，1，1。

输入格式

两个正整数n，k，中间用空格隔开。

输出格式

输出划分方案的总数。

数据范围

1≤n≤200，1≤k≤n。

输入样例

7 3

输出样例

4

算法1

(递归) $O(n^2)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

p1011 [noip1998 提高组] 车站

题目描述：

有一个车站，有n个人要上车，但是车只有m个座位，所以只有前m个人能够上车，后面的人只能等下一班车。现在有k辆车，每辆车的座位数也是m个，问最少需要多少时间才能让所有人都上车？

输入格式：

输入共k+1行，第一行包含三个整数n,m,k，分别表示总人数，每辆车的座位数，以及车的数量。

接下来k行，每行包含m个整数，表示每辆车上的人的编号，编号从1开始。

输出格式：

输出一个整数，表示最少需要的时间。

输入样例：

10 3 3
1 2 3
4 5 6
7 8 9
10

输出样例：

4

算法1

(贪心) $O(n)$

每辆车都坐满，这样可以保证最少的车次数。

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码