题目链接:JZOJ 6287
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
struct node{
long long key,val;
}e[N];
long long f[2][301][301],sum[400];
long long g[301][301];
bool cmp(const node&a,const node&b){
return a.key<b.key;
}
long long gcd(long long a,long long b){
if(a<b)swap(a,b);
while(a=a%b)swap(a,b);
return b;
}
int main(void){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
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;
long long n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>e[i].key>>e[i].val;
}
sort(e+1,e+n+1,cmp);
for(int i=1;i<=n;i++){
for(long long j=1;j<=n;j++){
g[i][j]=gcd(e[i].key,e[j].key);
}
}
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+e[i].val;
if(i!=1&&g[i][i-1]!=1)f[0][i][i]=e[i].val;
if(i!=n&&g[i][i+1]!=1)f[1][i][i]=e[i].val;
}
long long max0=-0x7fffffffffffffll,Dp;
for(int Len=2;Len<=n;Len++){
for(int l=1,r;l+Len-1<=n;l++){
r=l+Len-1;
for(int u=l;u<=r;u++){
if(u==l)Dp=f[0][l+1][r]+(sum[r]-sum[l-1]);
if(u==r)Dp=f[1][l][r-1]+(sum[r]-sum[l-1]);
if(l<u&&u<r)Dp=f[1][l][u-1]+f[0][u+1][r]+(sum[r]-sum[l-1]);
if(l!=1&&g[u][l-1]!=1)f[0][l][r]=max(f[0][l][r],Dp);
if(r!=n&&g[u][r+1]!=1)f[1][l][r]=max(f[1][l][r],Dp);
if(Len==n)max0=max(max0,Dp);
}
}
}
if(max0<0)cout<<"-1";
else cout<<max0;
return 0;
}
近期评论