【JZOJ6287】【NOIP提高组A】扭动的树

题目大意

给出(n)个二元组(<key,val>)，要求构造一棵以(key)为关键字的二叉搜索树，并且一条边两端的(key)的(gcd>1)。计(sum[u])表示(u)子树内(val)之和，求一个构造方案令(sum sum[u])最大。
(nleq 300,key leq 10^18,val leq 10^6)

分析

首先按(key)排序转换为中序遍历上的区间问题。

设(f_{i,j,k})表示区间([i,j])选(k)为根的最大值，转移(O(n^5))，过不了。。。。

然后就有一种经典的套路：

区间([i,j])只会以(i-1)或(j+1)为根。考虑设状态(f_{i,j,0/1})表示区间([i,j])以(i-1/j+1)为根的最大值，由于根已经确定，枚举就变得容易了，时间复杂度降低至(O(n^3))，空间复杂度(O(n^2))，实现时使用记忆化搜索即可。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 307;
const ll INF = (1ll << 45);

int n;
ll ans, f[N][N][2], sum[N], g[N][N];
struct node { ll k, v; } a[N];

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
int cmp(node p, node q) { return p.k < q.k; }

ll getf(int l, int r, int k)
{
	if (l > r) return 0;
	if (~f[l][r][k]) return f[l][r][k];
	ll ret = -INF;
	if (k) { for (int i = l; i <= r; i++) if (g[i][r + 1] > 1) ret = max(ret, getf(l, i - 1, 1) + getf(i + 1, r, 0) + sum[r] - sum[l - 1]); }
	else { for (int i = l; i <= r; i++) if (g[i][l - 1] > 1) ret = max(ret, getf(l, i - 1, 1) + getf(i + 1, r, 0) + sum[r] - sum[l - 1]); }
	return f[l][r][k] = ret;
}

int main()
{
	//freopen("tree.in", "r", stdin);
	//freopen("tree.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i].k, &a[i].v);
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = gcd(a[i].k, a[j].k);
	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i].v;
	memset(f, -1, sizeof(f));
	ans = -INF;
	for (int i = 1; i <= n; i++) ans = max(ans, getf(1, i - 1, 1) + getf(i + 1, n, 0) + sum[n]);
	if (ans < 0) printf("-1
");
	else printf("%lld
", ans);
	return 0;
}