[NOIP2013] [vijos1850] 어린이의 숫자(dp+욕심)

제목 설명

전송문

문제풀이

vijos 데이터가 너무 강한 것 같아요.코드vs에서 뛰었지만 카드 상수에 걸렸습니다.사실 이 문제의 뜻은 잘 알지만 나는 두 개의 구덩이를 발견했다. ①특징치를 계산할 때의 dp, f(i)는 i로 끝나는 가장 긴 연속 서열과 같기 때문에 최종적으로 어떤 사람의 특징치인 F(i)=f(j), 1<=j<=i.이 잘못은 대단히 옳지 않으니 이후에 주의해야 한다.② 많은 사람들이 당연하거나 대충 계산해 보면 롱롱을 넘지 않을 거라고 생각하지만 실제로는 충분히 가능하다.극단적인 상황: 106명의 어린이가 있고 모든 어린이의 숫자가 109라고 가정하면 그들의 특징치는 109, 2∗109, 3∗109...... 106𕑅109=1015이다.각 어린이의 점수는 109, 2, 4, 109......(1+(1+106), 109이어야 한다. 이것은 분명히 롱의 범위를 넘어섰다.사실 데이터는 비교적 양심적인 것이기 때문에 실제로는 극한이 아닌 상황에서도 롱롱롱을 터뜨리기 쉽다.그리고 또 하나는 하면서 모범을 보여서는 안 된다는 것이다.제목의 요구는 가장 큰 값을 구하고 다시 모형을 취하는 것이기 때문이다.직접 모형을 뽑으면 원래 큰 값이 다시 모형의 의미에서 작아질 수 있다.그럼 어떻게 해야 되지?우리는 첫 번째 어린이를 제외하고는 모든 어린이의 특징치와 점수가 떨어지지 않는다는 매우 유용한 성질을 발견할 수 있다.그러면 어떤 어린이의 경우 그의 점수는 두 가지 상황일 뿐이다. ① 만약에 그의 전 어린이의 특징치가 0보다 크다면 앞에 있는 모든 어린이의 특징치와 점수가 모두 떨어지지 않는 수열이라는 것을 의미한다. 그러면 이 어린이의 점수는 그의 전 어린이의 점수에 특징치를 더한다.① 만약에 이전의 어린이의 특징치가 0보다 작다면 앞의 모든 어린이의 특징치가 마이너스 수열이고 점수가 마이너스 상수열이라면 이 어린이의 점수는 두 번째 어린이의 점수에 특징치를 더한다.그리고 첫 번째 꼬마를 특판해.이 문제는 보급팀이지만 그래도 비교적 재미있다.worth a try.

코드

#include
#include
#include
using namespace std;
#define LL long long
#define N 1000005

const LL inf=1e18;
int n;
LL Mod,Max,a[N],f[N],g[N],h[N],ans;
bool flag;

int main()
{
    scanf("%d%lld",&n,&Mod);
    for (int i=1;i<=n;++i) scanf("%lld",&a[i]);
    f[1]=h[1]=a[1];Max=a[1];
    for (int i=2;i<=n;++i)
    {
        h[i]=max(h[i-1]+a[i],a[i]);
        f[i]=max(f[i-1],h[i]);
    }
    g[1]=f[1];g[2]=f[1]+g[1];
    if (g[2]>=g[1]) flag=true;
    for (int i=3;i<=n;++i)
    {
        if (f[i-1]>0)
        {
            g[i]=g[i-1]+f[i-1];
            if (g[i]>=g[1]) flag=true;
            if (g[i]>inf) g[i]%=Mod;
        }
        else g[i]=g[2];
    }
    if (!flag) ans=g[1]%Mod;
    else ans=g[n]%Mod;
    printf("%lld
",ans%Mod);
}

총결산

① dp는 범하지 말아야 할 실수를 피하고 상태를 잘 생각해야 한다.② 데이터 범위를 잘못 계산하지 말고 당연하다고 생각하지 마라.