题解 | 过河

动态规划

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int l,s,t,m, i, j;
    cin>>l>>s>>t>>m;
    int stone[l+1];
    for(i = 0;i<l;i++)
    {
        stone[i] = 0;
    }
    for(i = 0;i<m;i++)
    {
        cin>>j;
        stone[j] = 1;
    }
    vector<int> dp(l+s,INT_MAX);
    dp[0] = 0;
    for(i = s;i<l+s;i++)
    {
        for(j = s;j<=t;j++)
        {
            int prev_step = i-j;
            if(prev_step >= 0 && dp[prev_step] != INT_MAX)
            {
                dp[i] = min(dp[i],dp[prev_step]+stone[i]);
            }
        }
    }
    int res = 100;
    for(i = l;i<l+s;i++)
    {
        res = min(res, dp[i]);
    }
    cout<<res;
    return 0;
}