「NOIP 2004」合唱队形

记忆化搜索

定义一个 solve(x, lim, dir)

x 表示处理完的层数，所有x == n是就return

lim 是限制条件

dir 表示方向，true为向上，false向下

当 dir == true 时，显然有以下情况

• 若 height[x+1] > lim
• 选 solve(x+1, height[x+1], true)
• 不选 solve(x+1, lim, true)
• 若 height[x+1] < lim
• 不选 solve(x+1, lim, true)
• 选，并改方向 solve(x+1, lim, false)
• 若 height[x+1] == lim
• 只能跳 solve(x+1, lim, false)

当 dir == false时，不能再换方向，显然有以下情况

• 若 height[x+1] > lim
• 不选 solve(x+1, lim, false)
• 若 height[x+1] < lim
• 选 solve(x+1, height[x+1], false)

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
int t[101], dp[101][231][2], n, ans=200;
int solve(int x, int max,bool dir){
    if (x == n){
        return 0;
    }
    if (dp[x][max][dir]!=-1) return dp[x][max][dir];
    int& ans = dp[x][max][dir];
    if (dir){
        if (t[x+1] < max) return ans = std::min(solve(x+1,max,true)+1,solve(x+1,t[x+1],false));
        if (t[x+1] > max) return ans = std::min(std::min(solve(x+1,t[x+1],true),solve(x+1,max,true)+1), solve(x+1,t[x+1],false));
        return ans = solve(x+1,max,true)+1;
    }else{
        if (t[x+1] < max) return ans = std::min(solve(x+1,t[x+1],false),solve(x+1,max,false)+1);
        if (t[x+1] >= max) return ans = solve(x+1,max,false)+1;
    }
}
int main(){
    std::memset(dp, -1, sizeof(dp));
    int i;
    cin >> n;
    for (i=1;i<=n;++i)
        cin >> t[i];
    cout << solve(0,0,true);
    return 0;
}