Algoogle

Algorithm for Programming Contest

JOI 春合宿 2009 Chopsticks

Category: JOI Tag: dp

Chopsticks

問題概要


橋をN個の部分に分けて, それぞれの場所に塗る色が決まっている.
一度に塗れるのは連続した区間だけ.
重ね塗りをすることもできる(その場合色は上書きされる).
最小で何回塗れば目的の色にできるか.

解法


DPする.
dp[l][r] := 区間[l,r)を正しく塗るのに必要な最小回数
とすれば, 区間[l,r)はそれを2つに分解したものの和のうち最小になるものになるはず.
ただし区間の始点と終点が同じ文字の場合, 1回塗るのを省けることに注意する.

コード


(Chopsticks.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
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

inline void chmin(int &a, int b){a=min(a,b);}
int n, dp[512][512];
string s;

int solve()
{
        for (int len = 1; len <= n; len++) {
                for (int l = 0; l+len <= n; l++) {
                        int r = l+len;
                        dp[l][r] = r-l;
                        for (int m = l+1; m < r; m++)
                                chmin(dp[l][r], dp[l][m]+dp[m][r]);
                        if(r-l>1 and s[l] == s[r-1]) dp[l][r]--;
                }
        }

        return dp[0][n];
}

void input()
{
        cin >> n >> s;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments