HDU 6047 贪心思维题
Maximum Sequence
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1797 Accepted Submission(s): 842
Given two integer sequences {ai} and {bi} with the same length n, you are to find the next n numbers of {ai}: an+1…a2n
. Just like always, there are some restrictions on an+1…a2n
: for each number ai
, you must choose a number bk
from {bi}, and it must satisfy ai
≤max{aj
-j│bk
≤j<i}, and any bk
can’t be chosen more than once. Apparently, there are a great many possibilities, so you are required to find max{∑2nn+1ai
} modulo 109
+7 .
Now Steph finds it too hard to solve the problem, please help him.
For each test case, the first line consists of one integer n. The next line consists of n integers representing {ai}. And the third line consists of n integers representing {bi}.
1≤n≤250000, n≤a_i≤1500000, 1≤b_i≤n.
} modulo 109
+7。
分析可知 ,a_n+1-------a_2*n必定是一个非严格递减序列,由此可知对a_n+1-a_2*n有贡献的只可能是a_1-a_n+1(因为a_n+1-a_2*n是一个非严格递减序列)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
const int mod=1e9+;
int a[N],b[N],Max[N];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=;i<=n;++i) scanf("%d",&a[i]),a[i]-=i;
for(int i=;i<=n;++i) scanf("%d",&b[i]);
Max[n]=a[n];
for(int i=n-;i>=;--i) Max[i]=max(Max[i+],a[i]);
sort(b+,b+n+);
int ans1=Max[b[]]-n-,ans=Max[b[]];
for(int i=;i<=n;++i) ans=(ans+max(Max[b[i]],ans1))%mod;
printf("%d\n",ans);
}
}
最新文章
- python 3.5 成功安装 scrapy 的步骤
- android 7.0 学习笔记(一)
- js高级群的一些整理6月
- 用友ERP-U8最新破解(再次更新版本,附安装过程中的解决办法)
- hdu 5596 GTW likes gt
- WCF 编程实验室
- IT职业思考 谈谈IT外包公司
- 【循序渐进学Python】14.数据库的支持
- 装饰模式/decorator模式/结构型模式
- JSON认识
- ACM题目————Subsequence
- PAT 1021
- Window 点击“X”关闭之后无法show
- HDU 3903 Trigonometric Function
- CSS3知识点整理(五)----响应式设计及其他属性
- 你好 JSONP !!!!
- PERL学习笔记---正则表达式
- 解决使用Spring Boot、Multipartfile实现上传提示无法找到文件的问题
- spring+springmvc+hibernate 整合
- 【scapy】读取pcap