C语言网奉行“学练同步，知行合一”的学习理念，希望大家都能理论与动手一起加强！拒绝理论派！
每月月赛，最后一个周六晚八点开始，请提前预约参赛，参与排名！
混一天和努力一天，一天看不出任何差别，三天看不到任何变化，七天也看不到任何距离……
但是一个月后会看到话题不同，三个月后会看到气场不同，半年后会看到距离不同，一年后会看到人生道路截然不同。
请坚信你所喜爱的事物！
通知：举办比赛权限已经完全开放，支持老师、个人随时抽题创建校内赛等比赛，达到P2级即可
因比赛为公共资源，比赛名称建议包含学校/组织名称具有辨识度，比赛名称、公告不文雅、灌水将被删除比赛并取消权限！
题库的题不仅仅支持C语言C++、java，Python和php也可以提交
编程小组功能上线！欢迎各位老师、社团协会小组负责人申请创建，方便教学、训练！
申请优质题解的标准第一，代码格式工整整齐，第二，不少于300字的思路讲解，有配图更佳！
代码格式工整、有详细说明和配图的题解才有更多的浏览哦
学习交流 QQ1群156740915、4群 364137421、 211300176、博主群487133400 Python小组群 783851273 验证信息备注网站昵称！
个人资料中有关于自己联系地址、联系电话的信息，用于我们邮寄奖品福利等，且信息不会公开，别人看不到，请大家知晓！
注意，恶意创建比赛、直接复制代码发布无营养题解的行为，将被禁止相应权限！并扣除经验值! 申请恢复请联系管理员解除
本站题解请在题目内页-我要写题解发布，这样可以出现在题目题解列表页，还可以申请加优增加曝光哦！

lalalala

用户名：zhangshuo

访问量：109148

签　名：

像狗一样的学习，像绅士一样地玩耍。

等　　级
排　　名	4
经　　验	24262
参赛次数	10
文章发表	201
年　　龄	12
在职情况	学生
学　　校	芜湖市第十一中学
专　　业

　　自我简介：

今日懒惰流下的口水，将会成为明日里伤心的泪水。

TA的其他文章

C语言程序设计教程（第三版）课后习题7.4 （C++代码）
浏览：235

猥琐的打表！！
浏览：357

再度上映打表“圣人”
浏览：230

你可能喜欢

蛇行矩阵（C语言代码）
浏览：516

C二级辅导-等差数列（C++代码）
浏览：795

弟弟的作业（C++代码）
浏览：702

C二级辅导-阶乘数列（C语言代码）
浏览：536

点我有惊喜！你懂得！
浏览：772

在废了九牛二虎之力后——扭动的树——正解

　　作者: lalalala　　　　发表时间：2018-11-10 09:56:36 浏览：290　|　评论：1　

#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 人评分