[NOIP 2005] 강을 건너는 DP+ 경로 압축

3778 단어 DpNOIP

코드

#include 
#include 
#include 
#include 
using namespace std;

int l,s,t,m,a[1000],sz[10000000],f[10000000]={0},ans(0);
int main() {
    scanf("%d",&l);
    scanf("%d%d%d",&s,&t,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
    }
    if(s==t){
        for(int i=1;i<=m;i++){
            if(a[i]%s==0) ans++;
        }
        printf("%d
",ans);
        return 0;
    }
    sort(a+1,a+1+m);
    for(int i=1;i<=m;i++){
        if(a[i+1]-a[i]>90)a[i+1]=a[i]+(a[i+1]-a[i])%90;
    }
    if(l-a[m]>90) l=a[m]+(l-a[m])%90;
    for(int i=0;i<=l;i++){
        f[i]=1<<30;
    }
    for(int i=1;i<=m;i++){
        sz[a[i]]=1;
    }
    for(int i=s;i<=t;i++){
        if(sz[i]==1){
            f[i]=1; 
        }
        else f[i]=0;
    }
    for(int i=2*s;i<=l;i++){
        for(int j=s;j<=t;j++){
            if(j>i) break;
            f[i]=min(f[i-j],f[i]);
        }
        if(sz[i]==1){
            f[i]++;
        }
    }
    printf("%d
",f[l]);
    return 0;
}
Juria에서 파동을 가늠하는 걸 해보도록 하겠습니다.
핸드폰 번호 가리기 | 프로그래머스

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage