[문제풀이] 루구4170: [CQOI2007] 색칠

본제 전송문 구간 dpdp 명령어 dpi, jdp{i, j}dpi, j는 i-3-ji-ji-3-j를 바르는 최소 횟수 이동을 나타낸다.

d p i , i = 1 dp_{i,i}=1 dpi,i​=1

d p i , j = m i n ( d p i , j + 1 , d p i + 1 j ) ( s i = s j ) dp_{i,j}=min(dp_{i,j+1},dp_{i+1j})(s_i=s_j) dpi,j​=min(dpi,j+1​,dpi+1j​)(si​=sj​)

d p i , j = m i n ( d p i , j , d p i , k + d p k + 1 , j ) ( s i ! = s j ) dp_{i,j}=min(dp_{i,j},dp_{i,k}+dp_{k+1,j})(s_i!=s_j) dpi,j​=min(dpi,j​,dpi,k​+dpk+1,j​)(si​!=sj​)

Code:

#include 
#define maxn 100
using namespace std;
int dp[maxn][maxn];
char s[maxn];

int main(){
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 1; i <= n; ++i) dp[i][i] = 1;
	for (int l = 1; l <= n; ++l){
		for (int i = 1, j = 1 + l; j <= n; ++i, ++j){
			if (s[i] == s[j]) dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]);
			else for (int k = i; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
		}
	}
	printf("%d
", dp[1][n]);
	return 0;
}