#3872 扭动的树
描述
有一棵以key为键值以val为权值的二叉查找树，定义其某个节点的sum为它的子树内节点的val之和。给出n个(key, val)正整数对，现需保证这棵树上任意一条边的两个端点的key值的最大公约数不为1，询问这棵树上所有节点的sum之和最大可能是多少。如果这棵树不存在任意一个合法形态，输出-1。
输入
输入文件名为tree.in。
第一行为一个整数n。
接下来n行每行两个正整数ki vi。保证ki互不相同。
输出
输出文件名为tree.out。
输出仅一行一个整数表示答案。
提示
对于1号测试点（5%）：k_1=1。
对于1~3号测试点（15%）：1≤n≤10。
对于1~10号测试点（50%）：1≤n≤50。
对于11~14号测试点（20%）：所有ki的gcd不为1。
对于1~18号测试点（100%）：1≤n≤300,1≤k_i≤〖10〗^18,1≤v_i≤〖10〗^6。
标签
ZYH
区间DP，注意左右的最大值才有意义，同之前的机器人
code：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define N 100005 5 using namespace std; 6 struct node{ 7 long long key,val; 8 }e[N]; 9 long long f[2][301][301],sum[400]; 10 long long g[301][301]; 11 bool cmp(const node&a,const node&b){ 12 return a.key<b.key; 13 } 14 long long gcd(long long a,long long b){ 15 if(a<b)swap(a,b); 16 while(a=a%b)swap(a,b); 17 return b; 18 } 19 int main(){ 20 for(int i=0;i<=1;i++)for(int j=1;j<=300;j++)for(int k=1;k<=300;k++)f[i][j][k]=-0x7fffffffffffffll; 21 long long n; 22 cin>>n; 23 for(int i=1;i<=n;i++){ 24 cin>>e[i].key>>e[i].val; 25 } 26 sort(e+1,e+n+1,cmp); 27 for(int i=1;i<=n;i++){ 28 for(long long j=1;j<=n;j++){ 29 g[i][j]=gcd(e[i].key,e[j].key); 30 } 31 } 32 for(int i=1;i<=n;i++){ 33 sum[i]=sum[i-1]+e[i].val; 34 if(i!=1&&g[i][i-1]!=1)f[0][i][i]=e[i].val; 35 if(i!=n&&g[i][i+1]!=1)f[1][i][i]=e[i].val; 36 } 37 long long max0=-0x7fffffffffffffll,Dp; 38 for(int Len=2;Len<=n;Len++){ 39 for(int l=1,r;l+Len-1<=n;l++){ 40 r=l+Len-1; 41 for(int u=l;u<=r;u++){ 42 if(u==l)Dp=f[0][l+1][r]+(sum[r]-sum[l-1]); 43 if(u==r)Dp=f[1][l][r-1]+(sum[r]-sum[l-1]); 44 if(l<u&&u<r)Dp=f[1][l][u-1]+f[0][u+1][r]+(sum[r]-sum[l-1]); 45 if(l!=1&&g[u][l-1]!=1)f[0][l][r]=max(f[0][l][r],Dp); 46 if(r!=n&&g[u][r+1]!=1)f[1][l][r]=max(f[1][l][r],Dp); 47 if(Len==n)max0=max(max0,Dp); 48 } 49 } 50 } 51 if(max0<0)cout<<"-1"; 52 else cout<<max0; 53 return 0; 54 }
over