p1002.cpp

vijos动态规划5题:P1002,P1006,P1011,P1014,P1025

#include <cstdlib>
#include <iostream>
#include <cstring>

using namespace std;

int main(int argc, char *argv[])
{
    int l,s,t,m,n,i,j,k,x,d,last;
    int stone[101]={0},stonex[101]={0};
    int f[100001]={0},b[100001]={0},;
    cin>>l>>s>>t>>m;
    for(i=1;i<=m;i++)
    cin>>stone[i];
    x=0;
    if(s==t)
    {
        for(i=1;i<=m;i++)
        if(stone[i]%s==0)x++;
        cout<<x<<endl;
        return 0;
    }
    for(i=1;i<=m-1;i++)
     for(j=i+1;j<=m;j++)
     {
            if(stone[i]>stone[j])
            {
                x=stone[i];
                stone[i]=stone[j];
                stone[j]=x;
            }
        }
    d=0;last=0;
    for(i=1;i<=m;i++)
    {
        x=stone[i];
        x=x-d;
        if(x-last>72)
        {
            d+=x-last-72;
            l=l-(x-last-72);
            x=last+72;
        }
        b[x]=1;
        last=x;
    }
    if(l-last>72)l=last+72;
    for(i=1;i<=l;i++)f[i]=10000000;
    for(i=0;i<=l-s;i++)
     for(j=s;j<=t;j++)
     if(f[i+j]>f[i]+b[i+j])f[i+j]=f[i]+b[i+j];
    cout<<f[l]<<endl;
    system("PAUSE");
    return 0;
}