Given two integer sequences {ai} and {bi} with the same length n, you are to find the next n numbers of {ai}: an+1…a2nan+1…a2n. Just like always, there are some restrictions on an+1…a2nan+1…a2n: for each number aiai, you must choose a number bkbk from {bi}, and it must satisfy aiai≤max{ajaj-j│bkbk≤j<i}, and any bkbk can’t be chosen more than once. Apparently, there are a great many possibilities, so you are required to find max{∑2nn+1ai∑n+12nai} modulo 109109+7 .

Now Steph finds it too hard to solve the problem, please help him. 

　　数列要满足aj <= max{ai - i}，其中bk <= j < i，bk是数列b中的一项，且每个bk最多仅能取一次

　　看到这里肯定还看不明白。

　　具体说一下第一个样例：

　　　　a数组是8 11 8 5 　　b数组是3 1 4 2　　

　　　　现在要扩充a数组，然后数组的扩充方法是，a数组中每个数等于本身减去他的下标，然后从b数组中选一个数，然后a数组的这个数的位置开始到最后选一个最大的（只能解释到这样了）。

　　　　实现：a数组相当于 （8-1）（11-2）（8-3）（5-4）

　　　　从b数组中选择1，代表从a[1]到a[4]中选择一个最大的，选择9。然后将9添加到a数组中，然后数组为（8-1）（11-2）（8-3）（5-4） （9-5）

　　　　然后第二次从b数组中选择2代表从a[2]到a[5]中选择一个最大的，选择9。然后将9添加到a数组中，然后数组为（8-1）（11-2）（8-3）（5-4） （9-5）（9-6）

　　　　然后第三次从b数组中选择3代表从a[3]到a[6]中选择一个最大的，选择5。然后将5添加到a数组中，然后数组为（8-1）（11-2）（8-3）（5-4） （9-5）（9-6）（5-7）

　　　　然后第四次从b数组中选择4代表从a[4]到a[7]中选择一个最大的，选择4。然后将9添加到a数组中，然后数组为（8-1）（11-2）（8-3）（5-4） （9-5）（9-6）（5-7）（4-8）

　　然后更新完成了。最后数列a的n+1到2*n项的值为9+9+5+4=27

思路：

要想使数列a的n+1到2*a项最大，又每项都要减去i

所以应该尽量使bk最小，从最前面开始（可以理解为贪心）

那么肯定要先把最大的放进来

将b排序，计算ai - i的值

开一个max数组记录从i 到最后一项的最大ai-i的值（可以从后往前找）

每次加入点的时候，从后往前比较，如果小于这个数，就更新为这个数。

用一个sum记录总和。

记得每次加的结果要%mod。

注意数组要开为数据量的两倍，因为a数组要扩展！

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

int mod=1e9+;

using namespace std;

int a[],b[],maxx[];

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        memset(maxx,,sizeof(maxx));

        for(int i=; i<=n; i++)

        {

            scanf("%d",a+i);

            a[i]-=i;

        }

        for(int i=; i<=n; i++)

        {

            scanf("%d",b+i);

        }

        sort(b+,b+n+);

        maxx[n]=a[n];

        for(int i=n; i>=; i--)//更新max数组

        {

            maxx[i-]=max(a[i-],maxx[i]);

        }

        int flag=n+;

        int sum=;

        for(int i=; i<=n; i++)

        {

            sum+=maxx[b[i]];//选择最大的数

            a[flag]=maxx[b[i]]-(flag);

            maxx[flag]=a[flag];

            for(int j=flag-; j>=; j--)//加入新的点之后，要更新对应的max

            {

                if(maxx[j]<maxx[flag])

                    maxx[j]=maxx[flag];

                else break;

            }

            flag++;

            sum=sum%mod;

        }

        printf("%d\n",sum);

    }

}