rnqoj-15-采药--压缩区间

当s==t的时候，比较容易求。

当s<t 的时候，压缩相邻的两个石子之间的距离。任何距离大于150的石子间距都可以缩短到150.

这样dp求解就可以了

还有，一定要注意，石子不一定是有序的，在这里卡了很久，囧~~~

#include<stdio.h>  
#include<string.h>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
int l,s,t,m,ans;  
int a[151];  
int b[151];  
int dp[210000];  
void dos()  
{  
    int i,j,k;  
    sort(a+1,a+m+1);  
    for(i=1;i<=m;i++)  
    {  
        b[i]=b[i-1]+min(a[i]-a[i-1],150);  
    }  
    for(i=0;i<b[m]+150;i++)dp[i]=150;  
    dp[0]=0;  
    for(i=0;i<b[m]+150;i++)  
    {  
        for(j=s;j<=t;j++)  
        {  
            for(k=1;k<=m;k++)  
            {  
                if(i+j==b[k])  
                {  
                    dp[i+j]=min(dp[i+j],dp[i]+1);  
                    break;  
                }  
            }  
            if(k>m)dp[i+j]=min(dp[i+j],dp[i]);  
        }  
    }  
    ans=151;  
    for(i=b[m]+1;i<b[m]+150;i++)  
    {  
        ans=min(ans,dp[i]);  
    }  
    cout<<ans<<endl;  
}  
int main()  
{  
    int i;  
    cin>>l;  
    cin>>s>>t>>m;  
    for(i=1;i<=m;i++)  
    {  
        cin>>a[i];  
    }  
    ans=0;  
    if(s==t)  
    {  
        for(i=1;i<=m;i++)  
        {  
            if(a[i]%s==0)ans++;  
        }  
        cout<<ans<<endl;  
    }  
    else  
    {  
        dos();  
    }  
    return 0;  
}

补充：软件开发 , C++ ,