GRD3-T18: Wood Cutter

#include <bits/stdc++.h>
using namespace std;

const int L = 1000;
const int C = 50;

int cut[C + 1], dp[L + 1][L + 1];
int len, nCut;

int dpTopDown(int l, int r){
    int *upb = lower_bound(cut + 1, cut + nCut + 1, r) - 1;
    int *lwb = lower_bound(cut + 1, cut + nCut + 1, l);
    if(lwb > upb){
        return 0;
    }
    if(dp[l][r] != 0){
        return dp[l][r];
    }
    int mn = 1e9;
    for(int *ptr = lwb; ptr <= upb; ++ptr){
        mn = min(mn, dpTopDown(l, *ptr) + dpTopDown(*ptr + 1, r));
    }
    return dp[l][r] = r - l + 1 + mn;
}

int main(){

    scanf("%d %d", &len, &nCut);
    for(int i = 1; i <= nCut; ++i){
        scanf("%d", &cut[i]);
    }

    cout << dpTopDown(1, len);

    return 0;
}