尚未写完, 过几天会加几道蓝题紫题

---

咕咕咕

---

---

P1063 [NOIP2006 提高组] 能量项链

不难, 可以算模板题了.
d[l][r] 为区间 [l,r] 上能获取的最大值,
\(d[l][r] = max(d[l][i] + a[l] * a[i] * a[r] + d[i][r]), l<i<r\),
最终答案为 d[1][n].

#include <stdio.h>
#include <algorithm>
#define r l + len - 1

int n;
int a[203];
int d[203][203];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]), a[n + i] = a[i];
	for (int len = 3; len <= n * 2; len++)
		for (int l = 1; r <= 2 * n; l++) 
			for (int i = l + 1; i < r; i++)
				d[l][r] = std:: max(d[l][r], d[l][i] + a[l] * a[i] * a[r] + d[i][r]);
	
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans = std:: max(ans, d[i][i + n]);
	printf("%d\n", ans);
	return 0;
}

P1040 [NOIP2003 提高组] 加分二叉树

不难, 个人认为注释很清楚, 注意 root[l][r] 是指 d[l][r] 最小时的根, 以供输出最终方案.

#include <stdio.h>
#define ci const int &

int n;
int a[53]; 
int d[53][53];
int root[53][53];

inline void print2 (ci l, ci r) {
	if (l > r || r < 1 || l > n)
		return;
	if (l == r) {
		printf("%d ", l);
		return;
	}
	printf("%d ", root[l][r]);		// 根 
	print2(l, root[l][r] - 1);		// 左
	print2(root[l][r] + 1, r);		// 右 
	return;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]), d[i][i] = a[i], root[i][i] = i;
	for (int len = 2; len <= n; len++) {
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1; 
			
			// 情况 1, l 为根, 左子树为空 
			d[l][r] = d[l + 1][r] + d[l][l];
			root[l][r] = l;
			
			// 情况 2, i 为根, i∈(l,r) 
			for (int i = l + 1; i < r; i++)
				if (d[l][i - 1] * d[i + 1][r] + d[i][i] > d[l][r]) { 
					d[l][r] = d[l][i - 1] * d[i + 1][r] + d[i][i];
					root[l][r] = i; 
				} 
		}
	}
	printf("%d\n", d[1][n]);
	print2(1, n);
	printf("\n");
	return 0;
}

P4302 [SCOI2003]字符串折叠 | UVA1630 串折叠 Folding

题目的区别在于, 洛谷上的这题只需输出长度, 而 UVA 上需要输出最终字符

对于每一个区间 [l,r], 我们判断能否由两个区间合并得到和能否向后复制当前区间. 同时用 h 表示当前区间, mod 表示当前区间是如何得到的(两个都是输出最短字符用)

这里只贴 UVA 这题的代码了, 洛谷上的这题最终输出 d[1][n] 就可以了

#include <stdio.h>
#include <string.h>
#define ci const int &

int n = 0;
char a[105];
int d[103][103];
int h[103][103], mod[103][103];
inline int numlen (ci x) {
	if (x < 10)
		return 1;
	if (x < 100)
		return 2;
	return 3;
}
inline bool check (ci l, ci r, ci sr) {	// [l,r] 能否转为 [l,sr] 
	int len = r - l + 1, slen = sr - l + 1; 
	if (slen % len != 0)
		return false;
	for (int i = l; i <= sr; i++)
		if (a[i] != a[l + (i - l) % len])
			return false;
	return true;
}
inline void print (ci l, ci r) {
	if (mod[l][r] == 0) 
		for (int i = l; i <= r; i++)
			printf("%c", a[i]);
	else if (mod[l][r] == 1) {
		print(l, h[l][r]);
		print(h[l][r] + 1, r);
	}
	else {
		printf("%d(", (r - l + 1) / h[l][r]);
		print(l, l + h[l][r] - 1);
		printf(")"); 
	}
}
inline void sovle () {
	n = strlen(a + 1);
	memset(d, 0x3F, sizeof(d));
	for (int len = 1; len <= n; len++) 
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			if (len == 1)
				d[l][r] = len;
			else
			for (int i = l; i < r; i++)
				if (d[l][i] + d[i + 1][r] < d[l][r]) {
					d[l][r] = d[l][i] + d[i + 1][r];
					h[l][r] = i;
					mod[l][r] = 1;
				}
			for (int sr = r + len, cnt = 2; sr <= n && check(l, r, sr); sr += len, cnt++) {
				if (d[l][r] + 2 + numlen(cnt) < d[l][sr]) {
					d[l][sr] = d[l][r] + 2 + numlen(cnt);
					h[l][sr] = len;
					mod[l][sr] = 2;
				}
			}
		}
	print(1, n);
	printf("\n");
	return;
}
int main() {
	while (~scanf("%s", a + 1)) 
		sovle();
	return 0;
}

P4342 [IOI1998]Polygon

个人认为比上面那题难, 因为有个小点可能注意不到:
因为两个负数相乘是正数, 所以我们考虑同时保存每个区间可以得到的最大值和最小值, 同时需要增长数组至 2n 长, \(ans = max(d[i][i+n-1])\) 其中 \(1 <= i <= n\), 然后输出每一个满足 \(d[i][i+n-1]= ans\) 的 i 值即可.

#include <stdio.h>
#include <algorithm>
#define ci const int &

int n;
char ch[103];
int d[103][103];
int f[103][103];

inline int mathsovle (ci x, ci y, const char &op) {
	return (op == 't' ? (x + y) : (x * y));
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf(" %c %d", &ch[i], &d[i][i]), 
		ch[n + i] = ch[i],
		d[n + i][n + i] = d[i][i], f[i][i] = d[i][i], f[n + i][n + i] = d[i][i];
	for (int len = 2; len <= n; len++) 
		for (int l = 1; l + len - 1 <= 2 * n; l++) {
			int r = l + len - 1;
			d[l][r] = -0x3F3F3F3F, f[l][r] = 0x3F3F3F3F;
			for (int i = l; i < r; i++)
				d[l][r] = std:: max(d[l][r], mathsovle(d[l][i], d[i + 1][r], ch[i + 1])),
				d[l][r] = std:: max(d[l][r], mathsovle(f[l][i], f[i + 1][r], ch[i + 1])),
				d[l][r] = std:: max(d[l][r], mathsovle(d[l][i], f[i + 1][r], ch[i + 1])),
				d[l][r] = std:: max(d[l][r], mathsovle(f[l][i], d[i + 1][r], ch[i + 1])),
				f[l][r] = std:: min(f[l][r], mathsovle(d[l][i], d[i + 1][r], ch[i + 1])),
				f[l][r] = std:: min(f[l][r], mathsovle(f[l][i], f[i + 1][r], ch[i + 1])),
				f[l][r] = std:: min(f[l][r], mathsovle(d[l][i], f[i + 1][r], ch[i + 1])),
				f[l][r] = std:: min(f[l][r], mathsovle(f[l][i], d[i + 1][r], ch[i + 1]));
		}
	int ans = -0x3F3F3F3F;
	for (int i = 1; i <= n; i++) 
		ans = std:: max(ans, d[i][i + n - 1]);
	printf("%d\n", ans);
	for (int i = 1; i <= n; i++)
		if (d[i][i + n - 1] == ans)
			printf("%d ", i);
	printf("\n");
	return 0;
}