[CF 1155D] Beautiful Array

[CF 1155D] Beautiful Array - 1900

문제 설명 : 

n개의 수로 이루어진 수열과 x가 주어진다. 연속된 수들의 합의 최댓값을 구하면 되는데, 최대 1번에 한하여 수열의 연속된 수들에 x를 곱하는 연산이 가능하다.

풀이 : 

처음에 풀 때는 그리디하게 접근하려 했는데 WA를 받았다(반례 4 -1 / -5 10 -3 10).

아무튼 dp로 풀어야 하는데, 이 문제의 핵심은 결국 몇 번째부터 몇 번째까지 x가 곱해지냐이다(물론 안 곱할 수도 있다). 그래서 나는 x가 곱해지는 모든 구간의 경우에 대해서 저장하고 그 중에서 최댓값을 구하자는 취지이다. 일반화시키자면, 정답은 (x를 안 곱하는 구간) + (x를 곱하는 구간) + (x를 안 곱하는 구간) 으로 구성될 것이다. 그리고 나는 곱해지냐 안 곱해지느냐의 경계 지점만 찾으면 된다는 것이다. 그래서 dp테이블은 총 3개가 필요하다. 방금 언급했다시피 첫 번째는 안 곱할 구간, 두 번째는 곱할 구간, 세 번째는 안 곱할 구간이다. 이 3개의 경우를 적절히 더해서 최대가 되는 경우를 찾으면 된다. 첫 번째는 선택을 고려할 필요 없이, prefix sum이 0이상이 되도록만 만들어 주면 된다. 두 번째와 세 번째가 선택의 여지가 생기는데,  (k-1)번째 에서 값을 가져오느냐 k번째 에서 가져오느냐의 문제이다. 두 번째를 기준으로 설명하면 1번째에서 가져온다는 말은 현재 수부터 x를 곱할 것이라는 의미이고, 2번째에서 가져온다는 말은 이전부터 계속 x를 곱해왔던 수에 누적해나가는 뜻이다. 그래서 둘 중에 큰 값을 취하면 된다. 3번째도 마찬가지로 2번째와 3번째의 값을 비교하면 된다. 

주의할 점 : 

정답(최댓값)이 무조건 n번째 수에서 나온다는 보장은 없다. 그래서 i번째를 돌 때마다 dp[0][i]~dp[2][i]가 모두 정답의 후보가 될 수 있음에 주의해야 한다.

배운 점 : 

아직 dp유형 문제는 다른 유형에 비해서 부족한 것 같다. 처음에 접근할 때는 그리디로 푸는데 WA를 받거나 반례를 찾았을 때는 dp로 우회해야겠다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
inline vector<int> int_seperation(int N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 300009;
 
ll dp[3][SIZE];
ll arr[SIZE];
 
int main(){
    int n,x;    scanf("%d %d",&n,&x);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%lld",&arr[i]);
    }
 
    ll ans=0;
    for(int i=1 ; i<=n ; i++){
        dp[0][i]=max(0LL,dp[0][i-1]+arr[i]);
        dp[1][i]=max(dp[1][i-1],dp[0][i-1])+arr[i]*x;
        dp[2][i]=max(dp[2][i-1],dp[1][i-1])+arr[i];
 
        for(int j=0 ; j<3 ; j++){
            ans=max(ans,dp[j][i]);
        }
    }
 
    printf("%lld\n",ans);
    
    return 0;
}