글 읽기 - 특공대 CHT 구현 질문

ryute 5년 전 0

온라인에서 참고해서 CHT를 사용했는데 4퍼센트 즈음에서 틀렸습니다를 받습니다.

반례가 있는 건지 숫자가 커서 오버플로우가 나는 건지 모르겠습니다. 만약 아신다면 도움을 좀 주시면 감사하겠습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;

typedef long long ll;

int n,a,b,c;
vector<double> xpos;
vector<int> stk;
vector<int> V,S;
vector<ll> D;
int k; //이제 탐색을 시작해야 하는 번호 (스택 기준)

double cross(int p, int q) //p번째, q번째 직선의 교점 x좌표를 구함
{
    ll p1=-2LL*a*S[p], p2=(ll)a*S[p]*S[p]-(ll)b*S[p]+D[p];
    ll q1=-2LL*a*S[q], q2=(ll)a*S[q]*S[q]-(ll)b*S[q]+D[q];
    return (double)(q2-p2)/(double)(p1-q1);
}

int main()
{
    scanf("%d %d %d %d",&n,&a,&b,&c);
    V.assign(n,0); S.assign(n,0); D.assign(n,0);
    for(int i=0;i<n;i++)
        scanf("%d",&V[i]);
    partial_sum(V.begin(),V.end(),S.begin());

    for(int i=0;i<n;i++)
    {
        D[i]=(ll)a*S[i]*S[i]+(ll)b*S[i]+c;
        if(stk.size()==0) //맨 처음에 직선이 없으면 하나 넣어줌
        {
            stk.push_back(0);
            xpos.push_back(-1e18);
            continue;
        }
        while(k<stk.size()-1 && xpos[k+1]<S[i]) k++; //현재 i가 속하는 구간을 찾을때까지 우측으로 이동
        int j=stk[k];
        D[i]=max(D[i],D[j]+(ll)a*(S[i]-S[j])*(S[i]-S[j])+(ll)b*(S[i]-S[j])+c);
        while(stk.size()>1 && cross(stk.back(),i)<xpos[k]) // i번째 직선을 삽입하기 위해 쓸모없는 직선 삭제함
        {
            stk.pop_back();
            xpos.pop_back();
        }
        xpos.push_back(cross(stk.back(),i)); // i번째 직선 삽입
        stk.push_back(i);
        if(k>stk.size()-1) k=stk.size()-1; //만약 너무 많이 뺐으면 k를 같이 수정해 둠
    }
    printf("%lld",D[n-1]);
    return 0;
}

ryute 5년 전 0

구현은 myungwoo님 블로그 참고했습니다.

zlzmsrhak 5년 전 1

이 풀이가 맞는지 확인하려면, 적어도 CHT로 풀린다는 식 전개 과정이 있어야 할 것 같네요. 코드만 보고 확인하기에는 너무 비효율적입니다.

질문을 올릴 때, 자신이 어떤 식으로 문제를 풀었는지 쓰면 더 나은 답변을 얻을 수 있습니다.

일단 double은 값을 정확하게 저장하지 못할 수 있기 때문에, 되도록이면 정수나 분수 구조체를 정의해서 쓰는 것이 더 좋습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

특공대 CHT 구현 질문

ryute 5년 전 0

ryute 5년 전 0

zlzmsrhak 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말