#3872 扭动的树

 

描述

有一棵以key为键值以val为权值的二叉查找树，定义其某个节点的sum为它的子树内节点的val之和。给出n个(key, val)正整数对，现需保证这棵树上任意一条边的两个端点的key值的最大公约数不为1，询问这棵树上所有节点的sum之和最大可能是多少。如果这棵树不存在任意一个合法形态，输出-1。

输入

输入文件名为tree.in。

第一行为一个整数n。

接下来n行每行两个正整数ki vi。保证ki互不相同。

输出

输出文件名为tree.out。

输出仅一行一个整数表示答案。

样例输入[复制]

4

2 3

6 4

9 8

12 1

样例输出[复制]

51

提示

对于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
       
         2 #include
        
          3 #include
         
           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
          
           >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
           
          
         
        
       

over