即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

过河

编程语言 qq_35914587 20℃ 0评论

状压DP


QAQ


看这个题目啊,还是蛮简单的吧


很显然DP方程为dp[i]=min(dp[i],dp[i-j])


如果有石子,这个DP要+1的


可是这个范围,1e9,,,,,,,,,,


我很无奈啊,这咋办,我就是想水个题啊


看一下数据范围,m<=100也就是说,石子很稀疏,恩,很重要的信息


现在我们想一下,如果很长的一段区间之间内没有石子,我们的DP没有啥意义


这是一些不断的重新copy


于是我们的做法就是把石子的距离减小


从而达到快速的目的

#include 
#include 
#include 
#include 
using namespace std;
int dp[99999];
int d[99999];
int a[99999];
int ss[99999];
int k[9999];
int main()
{
    int l,s,t,m;

    scanf("%d%d%d%d",&l,&s,&t,&m);

    for(int i=1;i<=m;i++)
     scanf("%d",&a[i]);

    sort(a+1,a+m+1);

    for(int i=1;i<=m;i++)
     {
         d[i]=a[i]-a[i-1];
         k[i]=d[i]%t;
     }

     for(int i=1;i<=m;i++)
      {
        if(d[i]<=t+k[i]) 
            a[i]=a[i-1]+d[i];
        else a[i]=a[i-1]+t+k[i];
        ss[a[i]]=1;
      }

    int p=(l-a[m])%t;
    l=a[m]+t+p;
    memset(dp,0x7f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=l+t-1;i++)
     {
         for(int j=s;j<=t;j++)
          if(i-j>=0 && i-jif(!ss[i])
              dp[i]=min(dp[i],dp[i-j]);
            else
              dp[i]=min(dp[i],dp[i-j]+1);
         }
     }

    int ans=1e7; 

    for(int i=l;i<=l+t-1;i++)
     ans=min(dp[i],ans);

    printf("%d",ans);

    return 0;
}

转载请注明:CodingBlog » 过河

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情