DP Hrbust1186青蛙过河

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1186

 #include<stdio.h>

 #include<algorithm>

 #include<iostream>

 #include<string.h>

 using namespace std;

 int flag[];//记录该点是否有石子

 int dp[];//dp[i]表示走到i点所需要的最少石子数目

 int main()

 {

     int l,s,t,n;

     while(cin>>l>>s>>t>>n){

         memset(flag,,sizeof(flag));

         int k;

         for(int i=;i<n;i++){

             cin>>k;

             flag[k]=;

         }

         memset(dp,-,sizeof(dp));

         dp[]=;//初始位置

         for(int i=s;i<=l+t-;i++){对所有可能走到的点i进行遍历

             for(int j=i-t;j<=i-s;j++){对所有可能到达i的点遍历

                 if(j>=&&dp[j]!=-){

                     if(dp[i]==-)dp[i]=dp[j]+flag[i];

                     else dp[i]=min(dp[i],dp[j]+flag[i]);

                 }

             }

         }

         int mixn=;

         for(int i=l;i<=l+t-;i++){

            if(dp[i]!=-&&mixn>dp[i])

                 mixn=dp[i];

         }

         cout<<mixn<<endl;

     }

 }

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int l,s,t,n;

 int DP[]={};

 int main()

 {

     while(~scanf("%d%d%d%d",&l,&s,&t,&n))

     {

         memset(DP,,sizeof(DP));

         for(int i=;i<=n;i++)

         {

             int temp;

             scanf("%d",&temp);

             DP[temp]=;

         }

         for(int i=l-t-;i>=;i--)

         {

             int tmp=DP[i+s];

             for(int j=s+;j<=t;j++)

             {

                 tmp=min(tmp,DP[i+j]);

             }

             DP[i]+=tmp;

         }

         printf("%d\n",DP[]);

     }

     return ;

 }