[NOIP2005] 过河

考虑

因此对于两相邻点之间的距离可以对 取模离散化

然后正常 DP 即可

复杂度 .

#include<cstdio>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
int l,s,t,m,ans;
int a[101],d[101],f[300000];
int main(){scanf("%d%d%d%d",&l,&s,&t,&m);
    FOR(i,1,m)scanf("%d",&a[i]);
    sort(a+1,a+m+1);
    FOR(i,1,m)d[i]=a[i]-a[i-1],a[i]=a[i-1]+d[i]%2520,f[a[i]]=1;
    l=a[m]+t;
    FOR(i,1,l){
        int mn=m;    
        for(int j=s;j<=t&&j<=i;j++)mn=min(mn,f[i-j]);
        f[i]+=mn;
    }
    ans=m;
    FOR(i,l-t,l-1)ans=min(ans,f[i]);
    printf("%d",ans);
    return 0;
}

  转载请注明: Sshwy's Blog [NOIP2005] 过河

 上一篇
VIM 学习日志 VIM 学习日志
摘要 vim 大法好啊 Vim 插件安装首先安装 Vundle,见 Vundle-Github. 安装插件的时候,先在 vimrc 里面输入 Plugin 'XXX' 并保存,然后 vim 里运行 PluginInstal
2018.11.08
下一篇 
清北学堂 18 金秋模拟题 1 清北学堂 18 金秋模拟题 1
总结 最后 5 分钟,检查文件 IO,数组大小,关闭多余的调试信息。 题面 A.game概率 DP, 表示打 场赢 场的概率。最后统计期望即可 #include<cstdio> #define FO
2018.11.07
  目录