JOI春合宿 2009-day4 Chopsticks
問題文 : 塗り箸
解法 :
dp[i][j] : 区間[i, j]を塗るためのコストの最小値, とすると
dp[i][i] = 1,
dp[i][j] = for(k = i...j - 1) min(dp[i][k] + dp[k + 1][j]) - (t[i] == t[j])
となる. これは, 区間の幅を小さいものから計算すれば実現できる.
コード :
#include <cstdio> #include <algorithm> using namespace std; int main() { int n; char str[512]; unsigned int dp[512][512]; scanf("%d", &n); scanf("%s", &str[1]); for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ dp[i][j] = 0xdeadbeef; } dp[i][i] = 1; } for (int d = 1; d < n; d++){ for (int x = 1; x + d <= n; x++){ for (int mid = x; mid <= x + d; mid++){ dp[x][x + d] = min(dp[x][x + d], dp[x][mid] + dp[mid + 1][x + d]); } if (str[x] == str[x + d]) dp[x][x + d]--; } } printf("%u\n", dp[1][n]); }