noip2013 어린이의 숫자(dp)

제목 설명Description에는 n 명의 어린이들이 일렬로 줄을 서 있다.모든 어린이의 손에는 숫자가 하나 있는데, 이 숫자는 플러스마이너스다.모든 어린이의 특징치는 그의 앞(본인 포함)에 랭크된 어린이 중 몇 명(최소 한 명)의 어린이가 가지고 있는 숫자의 합의 최대치와 같다고 규정한다.이 어린이들의 선생님으로서 당신은 모든 어린이에게 점수를 주어야 합니다. 점수는 이렇게 규정되어 있습니다. 첫 번째 어린이의 점수는 그의 특징치이고 다른 어린이의 점수는 그의 앞에 있는 모든 어린이 중(본인을 포함하지 않음)이며 어린이의 점수는 그의 특징치의 최대치입니다.모든 어린이의 점수의 최대치를 계산하고 출력할 때 최대치의 기호를 유지하며 절대값을 p에 모형화한 후에 출력하십시오.
설명 Input Description 첫 번째 행은 두 개의 양의 정수 n, p 로 구성되며 공백으로 구분됩니다.두 번째 줄은 n개의 수를 포함하고 두 정수 사이를 빈칸으로 구분하여 모든 어린이의 손에 있는 숫자를 나타낸다.
출력 설명 Output Description 출력에는 최대 분수가 p로 모델링된 결과를 나타내는 정수가 포함된 줄이 한 줄만 있습니다.
샘플 입력 Sample Input [sample 1] 5 997 1 2 3 4 5 [sample 2] 5 7 - 1 - 1 - 1 - 1
샘플 출력 Sample Output [sample 1] 21 [sample 2] - 1 문제풀이: 주로 국어 능력을 고찰하고 관건은 문제를 읽는다.문제를 다 읽으면 이것이 가장 큰 자단과 문제라는 것을 알 수 있다.최대 하위 세그먼트와 문제에 대해 우리는 O(N)의 알고리즘을 가지고 있다.구체적인 방법은 다음과 같다. 현재 I위와 이전의 최대 자단과를 요구한다. 만약에 (I-1)위와 이전의 최대 자단과 0보다 크면 분명히 이 사람이 가져도 안 될 것이 없다. 즉, 현재의 이 자단이 앞의 자단과 연결되는 것이다.그렇지 않으면 앞의 최대 자단을 0으로 바꾼 다음 계속 아래로 스캔하세요.이게 꼭 DP라고 해도 돼요.이렇게 소박하게 하면 50점을 얻을 수 있다. 특징치와 점수를 계산하는 과정에서 최대치를 기록하면 80점을 얻을 수 있다. 왜냐하면 마지막 두 점과의 점수가 롱롱을 초과했기 때문이다.한층 더 분석해 보면 첫 번째 어린이를 제외한 나머지 어린이의 점수는 떨어지지 않는다는 것을 알 수 있다.그래서 한 어린이에 대한 그의 점수는 단지 두 가지 상황일 뿐이다.1. 만약에 그의 전 어린이의 특징치가 0보다 크면 그의 점수는 전 어린이의 점수에 전 어린이의 특징치를 더한다.현재 최대값을 업데이트합니다.2. 만약 그의 이전 어린이의 특징치가 0보다 작다면 그의 점수는 두 번째 어린이의 점수이다.한 어린이의 점수가 1000000000보다 많을 때 우리는 첫 번째 어린이의 점수가 1000000000보다 크지 않기 때문에 계산 과정에서 첫 번째 어린이의 점수가 첫 번째 어린이보다 큰지 판단할 수 있다.이렇게 하면 만점을 받을 수 있다.

#include
#include 
using namespace std;
long long maxx,a[1000001],n,m,p,f[1000001]={0},b[1000001],ff[1000001],ans;
bool zf;
int main()
{
    cin>>n>>p;
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    f[1]=a[1];maxx=a[1];
    ff[1]=a[1];
    for (int i=2;i<=n;i++)
      {
        f[i]=max(f[i-1]+a[i],a[i]);
        ff[i]=max(maxx,f[i]);
        maxx=ff[i];
     }
    b[1]=ff[1];
    b[2]=ff[1]+b[1];
    if (b[2]>=b[1]) zf=true;
    maxx=b[2];
    for (int i=3;i<=n;i++)
      {
         if (ff[i-1]>0)
           {
             b[i]=b[i-1]+ff[i-1];
             if (b[i]>b[1]) zf=true;
             if (b[i]>1000000000) b[i]%=p;
           }
         else
             b[i]=b[2];  
      }
    if (!zf) ans=b[1];
    else ans=b[n];
    ans%=p; 
    printf("%lld",ans);        
}