【铺设道路题解】无数组版最低时内版

原题链接：517.[NOIP 2018 提高组] 铺设道路

sczans.(3/4退站)

2026-07-22 15:39:21

发布于：河南

15阅读

0回复

0点赞

思路都在代码(在文末)里了

我们来说一说不用数组（降维）的情况和实例

代码降维

此题不用数组的本质是降维（1 维到 0 维），和背包DP 2 维降 1 维是一个意思

降维的情况：

对于一个 n 维状态空间的问题，若计算当前状态时，仅依赖于状态空间中维度差为 $q（0≤q≤n）$ 的历史状态，则可以将原本的n维存储结构，压缩为 $n-q$ 维的存储结构。

例如本题只需要循环用输入的相邻两个数判断，完全没必要存数组！

实例：

0维实例（q=n）：

// 计算1+2+...+n，无需数组存储中间结果
int sum = 0;
for(int i=1; i<=n; i++) sum += i;
//这里当前状态sum仅依赖前一步的sum和当前i，与更早的历史状态无关，完全不需要数组存储。

1维降0维实例：与本题有异曲同工之妙

// 斐波那契数列，用两个变量替代数组
int a=0, b=1;
for(int i=2; i<=n; i++){
    int c = a + b;
    a = b;
    b = c;
}
//原本需要1维数组存储所有斐波那契数，但当前状态仅依赖前两个状态，因此可以降为0维（仅用两个变量）。

2维降1维实例（经典背包问题）：

int dp[1001] = {0};
for(int i=0; i<n; i++){
    int w = weight[i], v = value[i];
    for(int j=1000; j>=w; j--){
        dp[j] = max(dp[j], dp[j-w] + v);
    }
}//原本需要n×W的二维数组，但当前状态仅依赖上一层的状态，通过逆序遍历可以将空间复杂度从O(nW)降为O(W)。

代码

#include<cstdio>
using namespace std;

int main(){
    int n,a1,a2,ans=0;
    scanf("%d",&n);
    scanf("%d",&a1);
    ans+=a1;// 初始化总天数
    //不需要存储每个值！直接用2个滚动变量，
    for(int i=2;i<=n;i++){
        scanf("%d",&a2);
        if(a1<a2)
            ans+=a2-a1;// 这区域的深度小于下一区域的深度，累加两者之差
        a1=a2;//更新a1
    }
    printf("%d",ans);
    return 0;
}