[욕심] AGC027B Garbage Collector

분석:

시험장에서 어떻게 잘못 생각했는지...
잘못된 DP를 생각했지만 그때는 발견하지 못했습니다...그리고 끊었어요...
사실 정해와 나의 DP는 차이가 많지 않아서 마침 반대로 (그렇게 많은 데이터를 넘길 수 있다는 것은 정말 기적이다) 나의 DP가 구한 것은 거의 최악의 해이다.
그렇게 많이 말하지 않아도 사실 똑똑히 생각하면 아주 간단한 문제이다. 로봇이 모두 kk번의 쓰레기를 버렸다고 가정하면 쓰레기를 버리는 대가가 이미 고정되었다(N*x+k*x). 지금은 도로에서 소모하는 대가를 요구하는 것이다.
사실 그 잘못된 DP를 통해서도 이 특징을 발견할 수 있다. 매번 쓰레기를 버리면 도로에서의 대가는 다음과 같다. 9.
이 양식을 관찰해 보면 매번 쓰레기를 버릴 때마다 대가가 가장 먼 두 개의 점*5+제3의 점*7+를 발견한다.
그러면 매우 직관적인 욕심의 사고방식은 바로 가장 먼 k의 점도*5, 가장 먼 k의 점도*5, 다시 먼 k의 점도*7이다.
그래서 K를 매거할 수 있다. 그리고 매번 가장 먼 K의 점의 화, 가장 먼 K의 점의 화...를 계산할 수 있다. 이것은 접두사와 O(1) 구간을 빌려 화합을 구할 수 있다.시간의 복잡도는 또 조화급수...

#include
#include
#include
#include
#define SF scanf
#define PF printf
#define MAXN 200010
using namespace std;
typedef long long ll;
ll a[MAXN],x,pre[MAXN],ans;
int n;
int main(){
    SF("%d%lld",&n,&x);
    for(int i=1;i<=n;i++){
        SF("%lld",&a[i]);
        pre[i]=pre[i-1]+a[i];
        ans+=a[i]*5ll+2ll*x;
    }
    for(int k=1;kfor(int j=n,cnt=1;j>0;cnt++){
            int j1=max(0,j-k);
            ll sum=pre[j]-pre[j1];
            res+=max(5ll,cnt*2ll+1ll)*sum;
            if(res>ans)
                break;
            j=j1;
        }
        ans=min(ans,res);
    }
    PF("%lld",ans+1ll*n*x);

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[noip2013] 꽃장인DP||욕심

화공의 동채에 한 줄의 꽃을 심었는데, 꽃마다 모두 자신의 높이가 있다.꽃은 자랄수록 커지고 비좁아진다.동동은 이 줄의 일부 꽃을 옮기고 나머지는 제자리에 남겨 남은 꽃이 자랄 수 있는 공간을 마련하기로 했다. 또한...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[욕심] AGC027B Garbage Collector

분석:

좋은 웹페이지 즐겨찾기