topcoder SRM 654 DIV2 1000 Successive Subtraction 2 문제 풀이(dp)

제목:
a1-a2-a3-a4-a5...an
q번 수정, 매번 한 위치의 수를 수정합니다.           
출력은 매번 수정이 끝난 후, 이 식에 대해 최대 두 개의 괄호 뒤의 최대치를 붙인다
n<=2000,q<=2000
문제 풀이:
매번 수정이 끝난 후에 동적 기획의 방법으로 O(n)의 복잡도를 가장 잘 구한다.
dp[i][j][k]로 현재 i위에 있고 j개의 괄호가 쓸모가 없음을 나타낸다. 앞에 k개의 유효한 앞괄호의 최우수값이 있다.
코드는 다음과 같습니다.

// BEGIN CUT HERE
// END CUT HERE
#line 4 "SuccessiveSubtraction2.cpp"
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <sstream>
#define OUT(x) cout << #x << ": " << (x) << endl
#define SZ(x) ((int)x.size())
#define FOR(i, n) for (int i = 0; i < (n); ++i)
#define inff 0x3fffffff
using namespace std;
typedef long long LL;
int dp[2100][3][3];
int val[2100];
int n;
int solve()
{
    int i,j,k;
    for(i=0;i<n;i++)
    {
        for(j=0;j<=2;j++)
        {
            for(k=0;k<=2;k++)
                dp[i][j][k]=-inff;
        }
    }
    dp[0][2][0]=val[0];
    for(i=1;i<n;i++)
    {
        for(j=0;j<=2;j++)
        {
            dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][0]-val[i]);
            if(j<2)
                dp[i][j][0]=max(dp[i][j][0],dp[i-1][j+1][1]-val[i]);
            if(j==0)
                dp[i][j][0]=max(dp[i][j][0],dp[i-1][2][2]-val[i]);
            if(j>0)
            {
                dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][1]+val[i]);
                dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][0]-val[i]);
                if(j==1)
                    dp[i][j][1]=max(dp[i][j][1],dp[i-1][2][2]+val[i]);
            }
            if(j==2)
            {
                dp[i][j][2]=max(dp[i][j][2],dp[i-1][j][2]-val[i]);
                dp[i][j][2]=max(dp[i][j][2],dp[i-1][j][1]+val[i]);
                dp[i][j][2]=max(dp[i][j][2],dp[i-1][j][0]-val[i]);
            }
        }
    }
    int re=max(dp[n-1][2][0],dp[n-1][1][0]);
    re=max(re,dp[n-1][0][0]);
    re=max(re,dp[n-1][1][1]);
    re=max(re,dp[n-1][2][1]);
    re=max(re,dp[n-1][2][2]);
    return re;
}
class SuccessiveSubtraction2
{
public:
    vector <int> calc(vector <int> a, vector <int> p, vector <int> v)
    {
        int i;
        n=a.size();
        vector<int>ans;
        for(i=0;i<n;i++)
        {
            val[i]=a[i];
        }
        int lp=p.size();
        for(i=0;i<lp;i++)
        {
            val[p[i]]=v[i];
            ans.push_back(solve());
        }
        return ans;
    }