2016 年沈阳网络赛---QSC and Master(区间DP)
2018-06-17 23:44:40来源:未知 阅读 ()
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=5900
Enter from the north gate of Northeastern University,You are facing the main building of Northeastern University.Ninety-nine percent of the students have not been there,It is said that there is a monster in it.
QSCI am a curious NEU_ACMer,This is the story he told us.
It’s a certain period,QSCI am in a dark night, secretly sneaked into the East Building,hope to see the master.After a serious search,He finally saw the little master in a dark corner. The master said:
“You and I, we're interfacing.please solve my little puzzle!
There are N pairs of numbers,Each pair consists of a key and a value,Now you need to move out some of the pairs to get the score.You can move out two continuous pairs,if and only if their keys are non coprime(their gcd is not one).The final score you get is the sum of all pair’s value which be moved out. May I ask how many points you can get the most?
The answer you give is directly related to your final exam results~The young man~”
QSC is very sad when he told the story,He failed his linear algebra that year because he didn't work out the puzzle.
Could you solve this puzzle?
(Data range:1<=N<=300
1<=Ai.key<=1,000,000,000
0<Ai.value<=1,000,000,000)
Each test case start with one integer N . Next line contains N integers,means Ai.key.Next line contains N integers,means Ai.value.
n
个pair<int , int>
,每次可以选相邻两个pair
。如果他们的first
不互质就可以把它们都删掉,并且获得second
之和的分数,问最大得分。#include <iostream> #include <algorithm> #include <stdio.h> #include <queue> #include <cmath> #include <string.h> using namespace std; long long a[305],b[305]; long long dp[305][305]; long long sum[305]; long long GCD(long long a,long long b) { return (b==0)?a:GCD(b,a%b); } int main() { int T,N; cin>>T; while(T--) { scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%lld",&a[i]); sum[0]=0; for(int i=1;i<=N;i++) { scanf("%lld",&b[i]); sum[i]=sum[i-1]+b[i]; } memset(dp,0,sizeof(dp)); for(int len=1;len<N;len++) { for(int i=1;i+len<=N;i++) { if(sum[i+len-1]-sum[i]==dp[i+1][i+len-1]) { dp[i][i+len]=dp[i+1][i+len-1]; if(GCD(a[i],a[i+len])>1) dp[i][i+len]+=b[i]+b[i+len]; } for(int k=i;k<i+len;k++) { dp[i][i+len]=max(dp[i][i+len],dp[i][k]+dp[k+1][i+len]); } } } printf("%lld\n",dp[1][N]); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 一个工业级、跨平台、轻量级的 tcp 网络服务框架:gevent 2020-06-05
- 2020年3月28日UCF Local Programming Contest 2016 2020-03-31
- 洛谷P4071-[SDOI2016]排列计数 题解 2020-01-12
- 【新年呈献】高性能网络通信框架 HP-Socket v5.7.1 2020-01-07
- 最小割最大流定理&残量网络的性质 2019-12-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash