题目大意：

给一个字符串，问需要至少覆盖多少次。

题目分析

区间dp： dp[i][j]表示达到i~j这个状态的最少覆盖次数，分两种情况：

s[i] == s[j]: 此时内层可能仍然相等或不相等，则

\[dp[i][j] = min(dp[i + 1][j], dp[i][j - 1], dp[i + 1][j - 1] + 1)
\]

以上括号中三种分别对应以下三种情况：

★☆☆☆☆★★， ★★☆☆☆☆★， ★☆☆☆☆☆★

s[i] != s[j]: 枚举断点k:

\[dp[i][j] = min\{dp[i][k] + dp[k + 1][j]\}
\]

code

#include<bits/stdc++.h>

using namespace std;

const int N = 100, OO = 0x3f3f3f3f;

char s[N];

int dp[N][N], len;

inline int DP(int l, int r){

	if(dp[l][r] != -1) return dp[l][r];

	if(l == r) return dp[l][r] = 1;

	int tmp = OO;

	if(s[l] == s[r]) tmp = min(tmp, min(DP(l, r - 1), min(DP(l + 1, r), DP(l + 1, r - 1) + 1)));

	else for(int k = l; k < r; k++) tmp = min(tmp, DP(l, k) + DP(k + 1, r));

	return dp[l][r] = tmp;

}

int main(){

	ios::sync_with_stdio(false);

	cin.tie(NULL), cout.tie(NULL);

	cin >> s + 1; len = strlen(s + 1);

	memset(dp, -1, sizeof dp);

	cout << DP(1, len);

	return 0;

}

巴特西

BZOJ 1260 - 区间dp

题目大意：

题目分析

code

最新文章

热门文章