M_sea

洛谷1052 过河
Luogu分析30分做法设$f[i]$表示前前i个长度,i必须踩的最小值。然后转移直接乱搞:($k[i]$表示是否...
扫描右侧二维码阅读全文
06
2018/10

洛谷1052 过河

Luogu

分析

30分做法

设$f[i]$表示前前i个长度,i必须踩的最小值。

然后转移直接乱搞:

$$f[i]=min_{j=i-t}^s{f[j]} + k[i]$$

($k[i]$表示是否是石头)

注意一下边界问题。

100分做法

数据跨度太大,而石头最多100个,所以间隙一定很大。

考虑把间隙缩短。可以证明,一定可以到达任意一个距离90以上的点。

那么在两个石头距离大于90时直接搞成90就行了。

PS:其实71也是可以的,详见NOIP2017D1T1。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[110];
int f[1000010];
int k[1000010];
int s,t,m,l;

int main() {
    l=read(),s=read(),t=read(),m=read();
    if (s>t) swap(s,t);
    for (re int i=1;i<=m;i++) a[i]=read();
    sort(a+1,a+m+1); l=0;
    if (s==t) {
        int ans=0;
        for (re int i=1;i<=m;i++)
            if (a[i]%s==0) ans++;
        printf("%d\n",ans);
        return 0;
    }
    for (re int i=1,pos=0;i<=m;i++) {
        if (a[i]-a[i-1]>90) pos+=90;
        else pos+=(a[i]-a[i-1]);
        k[pos]=1; l=max(l,pos);
    }
    memset(f,0x3f,sizeof(f));
    for (re int i=s;i<=t;i++) f[i]=k[i];
    for (re int i=s+s;i<=l+10;i++) {
        for (re int j=i-t;j<=i-s;j++)
            if (f[j]<f[i]) f[i]=f[j];
        f[i]+=k[i];
    }
    int ans=2147483647;
    for (re int i=l;i<=l+10;i++) ans=min(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 29 PM

发表评论

2 条评论

  1. ZCDHJ

    NOIP2018?? 毒奶预定

    1. M_sea
      @ZCDHJ

      手残了qwq改掉了