题解：P15433 [蓝桥杯 2025 国 Python B] 灯塔

Super_Diu · 2026-02-26 17:31:59 · 题解

基础 dp 题。

思路

用 v 数组保存灯塔 x 是否会被点亮，1 为有可能，0 为不可能。
推导状态转移方程：

dp_i = \begin{cases} \max(dp_{i-1}, dp_{i-2}+1), & v_i = 1, \\ dp_{i-1}, & v_i=0. \end{cases}

输出答案（dp_n）。

注意

记得初始化 dp_1 为 v_1。

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=1e6+10;
int n,m,dp[N],x;
bool v[N];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>x;
        v[x]=1; // 记录灯塔是否会被点亮
    }
    dp[1]=v[1]; // 记得初始化！
    for(int i=2;i<=n;++i){
        if(v[i]) // 状态转移
            dp[i]=max(dp[i-1],dp[i-2]+1);
        else
            dp[i]=dp[i-1];
    }
    cout<<dp[n]; // 输出
    return 0; // 完结撒花~
}