POI2014Little Bird

2928 단어 poi--단조로운 대기열
먼저 dp를 생각해야 한다. 그러면 dp[i]를 첫 번째 나무에 도착할 때의 최소 피로치로 정의한다.
그러면 dp이동을 할 때 두 점 간의 고도 크기 관계를 고려해야 하기 때문에 분류하여 토론해야 한다.
그럼 이런 dp는 O(n2)입니다.
그래서 최적화를 고려한다. 왜냐하면 우리는 한 점의 dp값이 앞의 k개만 옮길 수 있다는 것을 발견했기 때문에 단조로운 대기열을 사용하여 dp를 최적화하려고 한다.
그리고 어떤 값이 가장 좋은가요?
우선 dp값이 작은 것이 더 좋을 거예요!
dp값은 하나하나만 변화할 수 있기 때문에 고도의 차이가 어떻든 간에 dp값이 1보다 작으면 1의 대가를 통해 높이를 높일 수 있다.
그 다음에 고도의 차이이다. 같은 dp값의 경우 높이가 높은 것이 틀림없이 더 좋다. 왜냐하면 더 큰 공간을 가지고 선택할 수 있기 때문이다. 즉, 같은 높이이기 때문에 그의 dp값이 증가하지 않을 가능성이 더 크다.
그리고 단조로운 대기열로 최적화하면 되는데...
#include
#include
#include
#include
#define M 1000005
using namespace std;
void Rd(int &res){
    res=0;char p;
    while(p=getchar(),p<'0');
    do{
        res=(res<<1)+(res<<3)+(p^48);
    }while(p=getchar(),p>='0');
}
int q[M],dp[M],H[M],n,m;
bool Better(int x,int y){
    if(dp[x]return true;
    else if(dp[x]>dp[y])return false;
    return H[x]>=H[y];
}
int main(){
    Rd(n);
    for(int i=1;i<=n;i++)Rd(H[i]);
    Rd(m);
    for(int i=1;i<=m;i++){
        int k,l=0,r=0;Rd(k);
        q[r++]=1,dp[1]=0;
        for(int j=2;j<=n;j++){
            while(lk)l++;
            dp[j]=dp[q[l]]+(H[j]>=H[q[l]]);
            while(l1]))r--;
            q[r++]=j;
        }
        printf("%d
",dp[n]);
    }
    return 0;
}
스트림 수집기의 실제 예
TIL 15 | Semantic Web과 Semantic Tag

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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