mayoko’s diary

プロコンとかいろいろ。

SRM 654 div1 med:SuccessiveSubtraction2

よく考えると別に全然難しくなかった。

問題:TopCoder Statistics - Problem Statement

解法:数式を適当にいじると,数式のプラスとマイナスは
+[--...-][++...+][--...-][++...+][--...-]という形で出てくることがわかる。また,マイナスの区間からプラスの区間にするためにはカッコのペアを一つ消費する必要がある。よって,dp[n][phase][cnt]=(n個目の要素までにcnt回カッコを消費していて,現在のフェイズ(足し算するのか引き算するのか)はphaseになっているようなもので,題意の値が最大のもの)とすると,漸化式を作ることができる。
これをそれぞれのクエリに対して処理すれば良い。
以下ソースコード

const int MAXN = 2222;
int dp[MAXN][2][3]; // dp[n][phase][cnt]
const int INF = 1e9;

class SuccessiveSubtraction2 {
public:
    int solve(const vector<int>& a) {
//        cout << "TEST" << endl;
        int n = a.size();
        if (n == 1) return a[0];
        for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 3; k++) dp[i][j][k] = -INF;
        dp[1][0][0] = a[0]-a[1];
        for (int i = 1; i < n-1; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    if (dp[i][j][k] <= -INF) continue;
//                    cout << i << "  " << j << "  " << k << "  " << dp[i][j][k] << endl;
                    // 今の状態をそのまま維持
                    dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k] + ((j==0) ? (-a[i+1]) : a[i+1]));
                    // 今plusの状態の時はminusに戻せる
                    if (j == 1) dp[i+1][1-j][k] = max(dp[i+1][1-j][k], dp[i][j][k] - a[i+1]);
                    // 今minusの状態の時はkを一つ増やしてplusの状態にできる
                    if (j == 0 && k < 2) dp[i+1][1-j][k+1] = max(dp[i+1][1-j][k+1], dp[i][j][k] + a[i+1]);
                }
            }
        }
        int ret = -INF;
        for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) ret = max(dp[n-1][i][j], ret);
        return ret;
    }
    vector <int> calc(vector <int> a, vector <int> p, vector <int> v) {
        int q = p.size();
        vector<int> ret;
        for (int i = 0; i < q; i++) {
            a[p[i]] = v[i];
            ret.push_back(solve(a));
        }
        return ret;
    }
};