DP Hrbust1186青蛙过河

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<string.h>
 5 using namespace std;
 6 int flag[100020];//记录该点是否有石子
 7 int dp[100020];//dp[i]表示走到i点所需要的最少石子数目
 8 int main()
 9 {
10     int l,s,t,n;
11     while(cin>>l>>s>>t>>n){
12 
13         memset(flag,0,sizeof(flag));
14         int k;
15         for(int i=0;i<n;i++){
16             cin>>k;
17             flag[k]=1;
18         }
19 
20         memset(dp,-1,sizeof(dp));
21         dp[0]=0;//初始位置
22         for(int i=s;i<=l+t-1;i++){对所有可能走到的点i进行遍历
23             for(int j=i-t;j<=i-s;j++){对所有可能到达i的点遍历
24                 if(j>=0&&dp[j]!=-1){
25                     if(dp[i]==-1)dp[i]=dp[j]+flag[i];
26                     else dp[i]=min(dp[i],dp[j]+flag[i]);
27                 }
28             }
29         }
30         int mixn=100020;
31         for(int i=l;i<=l+t-1;i++){
32            if(dp[i]!=-1&&mixn>dp[i])
33                 mixn=dp[i];
34         }
35         cout<<mixn<<endl;
36     }
37 }