#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分)
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:562 |
【C语言训练】最大数问题 (C语言代码)浏览:528 |
九宫重排 (C++代码)浏览:1322 |
【绝对值排序】 (C语言代码)浏览:500 |
不容易系列2 (C语言代码)浏览:484 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:428 |
用筛法求之N内的素数。 (C语言代码)浏览:444 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:432 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:320 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:427 |
lalalala 2018-11-03 18:59:14 |
线段树维护