题目链接: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;
}
Greetings! I know this is kind of off topic but I was wondering which blog
platform are you using for this website? I’m getting sick and
tired of WordPress because I’ve had issues with hackers and
I’m looking at alternatives for another platform.
I would be great if you could point me in the direction of a good platform.