Topcoder SRM 654 Div2 1000

Problem

길이가 N(N∈[12000])인 수열 An(An∈[-3100100])에게 ans=A1 - A2 - 를 설정하고...--An, 다음에 M(M∈[12000])회 조작을 하고 매번 A의 p[i]의 값을 v[i], 즉 A[p[i]=v[i]로 수정한다. 매번 최대 2개의 괄호만 넣어서 ans 등식에 들어갈 수 있다. ans의 최대치가 얼마냐고 묻는다.

Solution

dp.. dp[i][j]를 설정하면 1부터 i-1까지 j개의 괄호가 있을 때의 최대치를 표시하고, j=0은 괄호가 없음을 표시하며, j=1은 (이렇게, j=2는 (이렇게, j=3은 ((()이렇게, j=4는 ((())이렇게)를 표시한다.없어.마지막으로 dp[n+1][j](0<=j<=4)의 최대치를 통계하면 됩니다.

My Code

//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
const double pi=acos(-1.0);
//const double eps=1e-9;
#define MOD 1000000007
#define MAXN 3000100
#define M
int dp[2010][10];
class SuccessiveSubtraction2{
public:
    int solve(vector<int>&a){
        for(int i=0;i<=a.size();i++){
            for(int j=0;j<=4;j++){
                dp[i][j]=-(1<<30);
            }
        }
        dp[0][0]=0;
        for(int i=0;i<a.size();i++){
            int x=(i?-a[i]:a[i]);
            dp[i+1][0]=max(dp[i+1][0],dp[i][0]+x);
            if(i>=2){
                dp[i+1][1]=max(dp[i+1][1],dp[i][0]-x);
                dp[i+1][1]=max(dp[i+1][1],dp[i][1]-x);
                dp[i+1][2]=max(dp[i+1][2],dp[i][1]+x);
                dp[i+1][2]=max(dp[i+1][2],dp[i][2]+x);
                dp[i+1][3]=max(dp[i+1][3],dp[i][2]-x);
                dp[i+1][3]=max(dp[i+1][3],dp[i][3]-x);
                dp[i+1][4]=max(dp[i+1][4],dp[i][3]+x);
                dp[i+1][4]=max(dp[i+1][4],dp[i][4]+x);
            }
        }
        int ret=-(1<<30);
        for(int i=0;i<=4;i++){
            ret=max(ret,dp[a.size()][i]);
        }
        return ret;
    }
    vector <int> calc(vector <int> a, vector <int> p, vector <int> v){
        int lenp=gsize(p);
        vector<int>res;
        res.clear();
        rep(i,0,lenp){
            a[p[i]]=v[i];
            int ans=solve(a);
            res.push_back(ans);
        }
        return res;
    }
};