Algoogle

Algorithm for Programming Contest

Typical DP Contest I - イウィ

Category: TDPC Tag: dp

I - イウィ

問題概要


解法


dp[l][r] := [l,r)で消せる文字の数の最大
として[l,r)の幅が小さいほうからDPする.
更新は区間を2つに分割したやつの和の最大をとっていく.
それの他に,区間の両端が’i’で,間の’w’で区切って区切られたの部分がそれぞれ全部消せるならdp[l][r] = r-lになる.

コード


(I.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repi(i,0,n)

char s[512];
int n, dp[512][512];

int solve() {
    repi(d,3,n+1) rep(l,n-d+1) {
        int r = l+d;
        repi(m,l,r) dp[l][r] = max(dp[l][r], dp[l][m]+dp[m][r]);
        if(s[l] != 'i' or s[r-1] != 'i') continue;
        repi(m,l+1,r-1) if(s[m] == 'w' and dp[l+1][m] == m-l-1 and dp[m+1][r-1] == r-m-2)
            dp[l][r] = r-l;
    }
    return dp[0][n]/3;
}

void input() {
    scanf("%s", s);
    n = strlen(s);
}

int main() {
    input();
    printf("%d\n", solve());
    return 0;
}

Comments