原题链接

突然有想法在洛谷搜石头门搜出来的题

这题挺有意思，本质上是求最优方案的结果，自然而然地想到可能需要用DP或是贪心，但是没有想到合适的子问题分解方式，最后看了题解，发现自己忽视了DP和贪心的基础：分治。鉴于之前从来没有做过纯粹的分治题目，这道题目对我来说十分有学习的价值

注意到问题的最优解不会超过$n$，也就是全部竖着刷的方案，在此基础上考虑是否能够找到更优解，这就用到了分治，以下摘一段来自OI-Wiki的解释：

分治算法的核心思想就是「分而治之」。

大概的流程可以分为三步：分解 -> 解决 -> 合并。

  • 分解原问题为结构相同的子问题。
  • 分解到某个容易求解的边界之后，进行递归求解。
  • 将子问题的解合并成原问题的解。

分治法能解决的问题一般有如下特征：

  • 该问题的规模缩小到一定的程度就可以容易地解决。
  • 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
  • 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

以前即使做DP和贪心也没有仔细考虑过分治的具体定义和特点，在此做一遍记录

该问题中，如果在全竖着刷的方案上进行改进，只能适当将一部分区域变为横着刷，由于只计次数，在条件允许的情况下从最左直接刷到最右没有任何坏处，自然想到唯一有可能减少原来竖着刷的次数的方法就是将画面中较短的矩形通过横刷完全覆盖掉，这样在这个矩形上就不用竖刷了，采取了这一方案后会产生一系列“被截断”的剩余矩形区间，根据题意显然这些剩余区间之间互相独立，如果也能求出这些区间的最优解，就可以相加计算出这个方案的结果并与初始方案比较是否更优，而这些剩余区间与当前的整个问题是同样的问题，可以采用递归的方式求解，最后能合并为整个题目的问题。每个问题都有两种选择，要么全竖着刷，要么尝试加入横着刷来得到更优的结果，而横着刷就需要求解一些子方案，采用分治法能够快速地对各级子方案进行尝试求解、筛选及合并得出原问题的最优解

从OI-Wiki上能够了解到，如果各个子问题之间存在重叠，分治法就会做许多重复的工作，这时候用DP就会更好，因为DP会存储决策过程中后续会用到的子问题的解，避免重复计算，可以说DP就是在分治的基础上进行了这样的改进

恰巧搜索到和学习这道题的思路加深了笔者对分治和DP的理解，这就不得不提到：这一切都是命运石之门的选择！（笑）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<algorithm>
#include<cstring>
#define fastIO ios_base::sync_with_stdio(false);cout.tie(0);cout.tie(0);
using namespace std;
const int N=5010,INF=0x3f3f3f3f;
// 命运石之门的选择 
// 答案不会超过n
// 这个题的重要特点：经分析可知仅存在两种有意义的方法可供选择，要在其中做出决策，可以用分治的方法寻找是否存在更优解
int n,h[N];
int solve(int l,int r,int t){
    if(l==r) return 1;
    int mi=INF,tmp=0,j;
    for(int i=l;i<=r;i++) mi=min(mi,h[i]);
    for(int i=l;i<=r;i++)
        if(h[i]>mi){
            for(j=i;h[j+1]>mi&&j<r;j++);
            tmp+=solve(i,j,mi);
            i=j;
        }

    return min(mi+tmp-t,r-l+1);
}

int main(){
    fastIO
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    cout<<solve(1,n,0)<<endl;

    return 0;
}