#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分
1 人评分
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:1435 |
C语言程序设计教程(第三版)课后习题7.2 (Java代码)浏览:681 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:525 |
c primer plus 第十二章 12.1小节浏览:377 |
最长单词 (C语言代码)浏览:1363 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:624 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:613 |
C语言考试练习题_一元二次方程 (C语言代码)浏览:576 |
Cylinder (C语言描述,蓝桥杯)浏览:1247 |
母牛的故事 (C语言代码)浏览:549 |
lalalala 2018-11-03 18:59:14 |
线段树维护