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++ 代码

相关问题

P1017 [NOIP2000 提高组] 进制转换

### NOIP2000 提高组进制转换题目解析

对于NOIP2000提高组中的进制转换问题，虽然具体题目未直接提及[^1]，可以借鉴其他年份相似类型的题目及其解决方法来进行分析。

#### 进制转换基本原理

在计算机科学中，不同进制之间的相互转化是一个基础知识点。通常涉及的是二进制、八进制、十进制以及十六进制间的互转。例如，在处理这类问题时，会先将给定数值由原进制形式转化为易于操作的形式——通常是十进制，然后再按照目标进制的要求重新表示出来。

针对特定场景下的进制转换：

- **从低级到高级**：当需要从小于等于十进制（如二进制或八进制）向更高位数的进制转变时，可以通过不断除以新基数并记录每次相除所得余数的方式完成。

- **从高级到低级**：相反地，如果是要降低当前使用的进制，则应采用乘法累积的方法逐步构建新的表达方式。

考虑到NOIP竞赛的特点，参赛者可能会遇到如下两种主要情况之一：

##### 十进制与其他任意进制间互相转换

此过程相对直观简单，只需遵循上述提到的原则即可实现自动化编程解答。比如要将一个十进制整数`N`转变为指定的目标进制`B`:

def decimal_to_base(N, B):
    result = ""
    while N != 0:
        remainder = N % B
        result += str(remainder)
        N //= B
    return result[::-1] or "0"

##### 多种非十进制之间直接转换

这种情况下，最简便的做法往往是先统一至十进制作为中间桥梁，之后再做进一步变换。即先利用已知规则把源数据映射回十进制空间内，随后依据目的端的需求调整其表现形态。

---

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++ 代码