rt，写了个奇怪的代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int read() {
	char ch = getchar();
	int x = 0;
	bool f = 1;
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = 0;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return f ? x : -x;
}
int n;
int a[35];
ll mem[35][35][35];
int nxt[35][35][35][2];
ll search (int rt, int l, int r) {
	if (l == r) {
		return a[rt];
	}
	if (mem[rt][l][r] != -1)
		return mem[rt][l][r];
	ll v1 = 1, v2 = 1, dt1 = 0, dt2 = 0;
	for (int i = l; i < rt; i ++) {
		int v = search (i, l, rt - 1);
		if (v > v1) {
			v1 = v;
			dt1 = i;
		}
	}
	for (int i = rt + 1; i <= r; i ++) {
		int v = search (i, rt + 1, r);
		if (v > v2) {
			v2 = v;
			dt2 = i;
		}
	}
	nxt[rt][l][r][0] = dt1;
	nxt[rt][l][r][1] = dt2;
	return mem[rt][l][r] = v1 * v2 + a[rt];
}
int pre[35];
void run (int p, int l, int r) {
	int q1 = nxt[p][l][r][0], q2 = nxt[p][l][r][1];
	printf ("%d ", p);
	if (q1 != 0) {
		run (q1, l, p - 1);
	}
	if (q2 != 0) {
		run (q2, p + 1, r);
	}
}
int main () {
	memset (mem, -1, sizeof(mem));
	n = read();
	for (int i = 1; i <= n; i ++) {
		a[i] = read();
	} 
	ll ans = 1;
	int rt = 1;
	for (int i = 1; i <= n; i ++) {
		int v = search (i, 1, n);
		if (v > ans) {
			ans = v;
			rt = i;
		}
	}
	printf ("%lld\n", ans);
	run (rt, 1, n);
}

第5个点 WA 了

输入

25
9 8 9 9 5 7 4 2 2 4 5 6 7 8 9 3 3 4 5 1 2 1 2 3 2

正确输出

781495238
8 4 2 1 3 6 5 7 16 12 10 9 11 14 13 15 20 18 17 19 23 21 22 24 25

我的代码输出

781495238
8 4 2 1 3 6 5 7 16 12 10 9 11 14 13 15 20 18 17 19 23 21 24 25 

没有输出 22

求差错 /kk