낙곡P1052강 건너기(NOIp2005)

3377 단어 DP--- 일반 DP낙곡Blog 칼럼

DP


제목 전송문
DP는 거리를 어떻게 압축하는지 비교적 잘 생각할 것이다.
L은 1e9이 있고 s와 t는 10밖에 없기 때문에 우리는 s와 t에 대해 글을 쓸 수 있다.압축 거리는 아무리 뛰어도 최종 상태가 등가라는 것을 보장해야 한다.
lcm=LCM(s,s+1,...,t)을 설정하면 모든 간격이 >lcm인 돌에 대해 거리를%lcm+lcm로 설정합니다.왜냐하면 아무리 뛰어도 lcm까지는 뛸 수 있기 때문이다.두 돌 사이에는 돌이 없기 때문에lcm덩어리를 절약할 수 있다.그리고 바로 DP를 만들면 돼요!
코드:
#include
#include
#include
#define MAXN 1000000
using namespace std;
int s,t,l,n,lcm;
int f[MAXN+5],a[MAXN+5],st[MAXN+5];
int gcd(int a,int b){
    if (!b) return a;
    return gcd(b,a%b);
}
int main(){
    scanf("%d%d%d%d",&l,&s,&t,&n);
    lcm=1;
    for (int i=s;i<=t;i++) lcm=lcm*i/gcd(lcm,i);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int k=0;
    for (int i=1;i<=n;i++){
        int m=a[i]-a[i-1];//    
        if (m>lcm) m=m%lcm+lcm;
        st[k+m]=1; k+=m;
    }
    memset(f,0x3f,sizeof(f)); f[0]=0;
    for(int i=s;i<=k+t;i++){//DP
        for (int j=s;j<=t;j++)
            f[i]=min(f[i-j],f[i]);
        f[i]+=st[i];//st[i]         
    }
    int ans=1e8;
    for (int i=k;i<=k+t;i++)//       ，         k+t
        ans=min(ans,f[i]);
    printf("%d
",ans);
    return 0;
}
semantic URL, supervisor
Resiliência em aplicaões.Netcom 폴리

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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