在废了九牛二虎之力后——扭动的树——正解

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm> 
using namespace std;
const int N=330;
typedef long long l1;
struct P{
	l1 k;
	int v;}a[N];
int n,i,j,k,p;
l1 l[N][N],r[N][N],g[N][N],f,t[N][N],s[N];
bool cmp(P u,P v)
{
	return u.k<v.k;} 
l1 gcd(l1 x,l1 y)
{
	return y?gcd(y,x%y):x;}
l1 max(l1 x,l1 y)
{
	return x>y?x:y;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%lld%d",&a[i].k,&a[i].v);
	sort(a+1,a+n+1,cmp);
	for(i=1;i<=n;i++)
	   for(j=1;j<=n;j++)
	       g[i][j]=gcd(a[i].k,a[j].k);
		   for(i=1;i<=n;i++)
		      s[i]=s[i-1]+a[i].v;
		    for(p=0;p<n;p++)
		    for(i=1;i+p<=n;i++)
		       {
			      t[i][j=i+p]=-1;
			      for(j=i+p,k=i;k<=j;k++)
			        {
				       if((k!=i&&!l[i][k-1])||(k!=j&&!r[k+1][j]))continue;
				       f=l[i][k-1]+r[k+1][j]+s[j]-s[i-1];
				       t[i][j]=max(t[i][j],f);
				       if(g[i-1][k]!=1)r[i][j]=max(r[i][j],f);
				       if(g[k][j+1]!=1)l[i][j]=max(l[i][j],f);			}
		    }
	printf("%lld",t[1][n]);
	return 0;
}

令人出乎意料——
深搜（60分）+树形结构（40分）