首页 > 其他 > 详细

P1052 过河

时间:2018-12-12 23:33:43      阅读:223      评论:0      收藏:0      [点我收藏+]

  一道很好的题,我给的标签:dp,数论,还要用到路径压缩。

  一开始我的想法是剪枝的搜索,但是当我看到数据范围的时候,就彻底放弃了这个想法……109啊……(吓人)

  那怎么办啊……

  路径压缩啊~

  对于为什么能路径压缩,在此简单解释一下:(感谢洛谷题解的提示)

  假设每次走p或者p+1步.我们知道\gcd(p,p+1)gcd(p,p+1)=1.

  由扩展欧几里得可知,对于二元一次方程组:

  px+(p+1)y=gcd(p,p+1)px+(p+1)y=gcd(p,p+1)是有整数解的,即可得:px+(p+1)y=s是一定有整数解的。

  设px+(p+1)y=spx+(p+1)y=s的解为:x=x0+(p+1)t,y=y0-pt。令0<=x<=p(通过增减t个p+1来实现),s>p*(p+1)-1,

  则有:y=(s-px) / (p+1)>=(s-p^2) / (p+1)>(p*(p+1)-1-px) / (p+1)>=0,y=p+1,s?px?>=p+1,s?p2?>p+1,p?(p+1)?1?px?>=0

  即表示,当 s>=p*(p+1)s>=p?(p+1) 时,px+(p+1)y=s, 有两个非负整数解,每次走p步或者 p+1 步,p*(p+1) 之后的地方均能够到达。

  如果两个石子之间的距离大于 p*(p+1)p?(p+1) ,那么就可以直接将他们之间的距离更改为 p*(p+1) 。

  差不多了。

  综上,得到压缩路径的方法:若两个石子之间的距离> t*(t-1),则将他们的距离更改为 t*(t-1) 。

  因为 t<=10t<=10 ,因此我们可以直接将大于10*9的距离直接化为90。

  但是要注意,对于 s=t 这种特殊情况,这种方法是不成立的应为在这种情况下,每次是不能够走p+1步的,因此需要另外特殊判断。

  下面是代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 20005
#define INF 99999999
int dp[maxn],far[maxn],a[maxn],st[maxn];
int dis,s,t,n;
int main()
{
    scanf("%d%d%d%d",&dis,&s,&t,&n);
    int total=0;
    if(s==t)
    {
        int fir;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&fir);
            total+=((fir%s)==0);
        }
        printf("%d",total);
        return 0;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);//a[i]->第i个石头的位置
     sort(a+1,a+n+1); 
     a[0]=0,far[n+1]=min(dis-a[n],90);
     dis=0;
     for(int i=1;i<=n;i++)
     {
         far[i]=min(a[i]-a[i-1],90);
         dis+=far[i];
         st[dis]=1;
     }
    dis+=far[n+1];
    dp[0]=0;
    for(int i=1;i<=dis+9;i++)
    {
        dp[i]=INF-1;
        for(int j=s;j<=t;j++)
        if(i>=j) dp[i]=min(dp[i],dp[i-j]+st[i]);
    }
    int minn=INF;
    for(int i=dis;i<=dis+9;i++)
    minn=min(minn,dp[i]);
    printf("%d",minn);
    return 0; 
}

  我发现:fir不写&的话也能得80分呢……

P1052 过河

原文:https://www.cnblogs.com/popo-black-cat/p/10111421.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!