P4302 [SCOI2003]字符串折叠

对于字符串的区间dp 寻找叠加后的最小值 其中叠加转化后的括号和数字均算为字符串长度
唯一的难度就是去想到怎样判断字符串是否可以折叠
我们可以只判断一个区间中整个字符串是否可以完全折叠为一个 其他的直接相加即可
题目链接

我们用f[i][j]来表示从i到j处理后的字符串最小长度 所以有
如果f[i][j]可以完全叠加 则为min(f[i][j], 叠加后长度 + 2 + 个数)

用一个check函数来判断字符串是否可以叠加

void check(int l, int r, int len)
{
	for (int i = l; i <= r; i ++ )
		if (st[i] != st[(i - l) % len + l]) return false;
	return true;
}

#include 

using namespace std;

const int N = 110;

string st;
int n, m[N];
int f[N][N];

bool check(int l, int r, int len)
{
	for (int i = l; i <= r; i ++ )
		if (st[i] != st[(i - l) % len + l]) return false;
	return true;
}

int main()
{
	cin >> st;
	n = st.size();
	st = ' ' + st;
	
	for (int i = 0; i <= 9; i ++ ) m[i] = 1;
	for (int i = 10; i <= 99; i ++ ) m[i] = 2;
	m[100] = 3;
	
	memset(f,0x3f, sizeof f);
	for (int i = 1; i <= n; i ++ ) f[i][i] = 1;
	
	for (int len = 2; len <= n; len ++ )
		for (int i = 1; i + len - 1 <= n; i ++ )
		{
			int j = i + len - 1;
			for (int k = i; k < j; k ++ )
				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
			for (int k = i; k < j; k ++ )
			{
				int slen = k - i + 1;
				if (len % slen != 0) continue;
				if (check(i, j, slen)) 
					f[i][j] = min(f[i][j], f[i][k] + 2 + m[len / slen]);
			}
		}
		
	printf("%dn", f[1][n]);
	
	return 0;
}