HDU6047 Maximum Sequence

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6047

题目意思

给你两个数组a，b。没个数组都有n个元素，接着求a【n+1】到啊【2*n 】，而a[i]=max{a[j]-j},b[k]

解题思路

根据题目可以知道每次a组值因为不断求出新的ai值而改变，所以设个dp数组存储区间的最大值，还有b数组限制着j能取的范围，而b数组的值的选择可以从小到大选，（比如b[3]值就能满足让ai取得最大，那么比b[3]小的值一定也满足，所以先消耗小的值）。具体看代码

代码部分

#include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <algorithm> #define MAXN 500050 #define ll long long using namespace std; const int MOD=1e9+7; int main() { int n; ll d[MAXN];///存放a[b[k]]到a[i-1]的最大值 while(~scanf("%d",&n)) { ll a[MAXN]; int c,b[MAXN]; memset(d,0,sizeof(d)); a[0]=0; b[0]=0; for(int i=1; i<=n; i++) { scanf("%d",&c); a[i]=c-i;///直接存放a[i]-i的值 } for(int i=1; i<=n; i++) { scanf("%d",&b[i]); } sort(b+1,b+n+1);///将b排序，下标从1开始到n int y=n,k=1,i=0,pos; ll sum=0;///由于结果可能非常大，所以用long long，否则会WA掉 while(y<2*n)///当y>=2*n时，说明已经a[n]到a[2n]的值已全部算出 { if(i>n&&a[i]<d[b[k-1]]&&b[k]<=pos) ///如果循环不是第一次，则a中已经插入了新的值，需要比较新的值与之前的最大值的大小 ///如果之前的最大值的位置pos在新的b[k]之后，则最大值可以不变，直接赋给新的d[b[k]] ///用这个判断可以减少好多次后面的循环，节省好多时间，否则会时间超限 d[b[k]]=d[b[k-1]]; else for(i=b[k]; i<=y; i++)///循环来得到a[b[k]]到a[i]的最大值 { d[b[k]]=max(d[b[k]],a[i]); if(d[b[k]]==a[i])pos=i;///记录最大值的下标 } i=y+1; a[i]=d[b[k]]-i;///将得到的值减去它的下标存到a数组中 sum=(sum+d[b[k]])%MOD;///将得到的a[i]的值加入总和，并每次都取余 k++;///b[k]的值只能使用一次，所以k++ y++;///将需要取最大值的区间的右边界加1，来将新加入的值包含到区间内 } printf("%lld\n",sum); } }