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 [NOIP 2000 提高组] 进制转换

### NOIP 2000 提高组 进制转换 解法

对于正整数的任意进制转换问题，核心在于理解和实现不同进制之间的相互转化算法。此过程主要涉及两个方面：一是将十进制数转化为目标进制下的表示；二是处理可能存在的大数值计算。

#### 十进制转其他进制

当把一个十进制数N转换为目标基数B时，可以通过不断除以基底并记录每次相除后的余数来完成这一操作。具体来说，在每一次迭代过程中，当前值被新的商取代直到其变为零为止。所有收集起来的余数组成了最终的结果序列，只是顺序相反需反转输出[^1]。

#include <iostream>
#include <vector>

using namespace std;

void convertToBase(int number, int base) {
    vector<int> result;
    
    while (number != 0) {
        result.push_back(number % base);
        number /= base;
    }
    
    // 反转结果以便正确显示
    reverse(result.begin(), result.end());
    
    for(auto &digit : result){
        cout << digit;
    }
}

需要注意的是，上述方法适用于任何大于等于2且小于等于10的目标进制。如果要支持更大的进制，则还需要额外定义字符集用于表示超过9的部分（例如A代表10,B代表11等等）。此外，考虑到题目描述提到输入可能是含零的情况，因此程序设计之初就应该能够接受非严格意义上的“正整数”。

#### 大数运算考量

由于涉及到较大范围内的数字变换，可能会遇到超出标准数据类型的存储极限的情形。此时应采用字符串或者其他形式的大数类来进行精确计算，从而避免因溢出而导致错误答案的发生[^4]。

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"

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

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

---