“科林明伦杯”哈尔滨理工大学第七届程序设计团队赛 I.Aggie’s Tasks(带权的LIS)

Description

Aggie is faced with a sequence of tasks, each of which with a difficulty value di and an expected profit pi. For each task, Aggie must decide whether or not to complete it. As Aggie doesn’t want to waste her time on easy tasks, once she takes a task with a difficulty di, she won’t take any task whose difficulty value is less than or equal to di.

Now Aggie needs to know the largest profits that she may gain.

Input

The first line consists of one positive integer t (t ≤ 10), which denotes the number of test cases.

For each test case, the first line consists one positive integer n (n ≤ 100000), which denotes the number of tasks. The second line consists of n positive integers, d1, d2, …, dn (di ≤ 100000), which is the difficulty value of each task. The third line consists of n positive integers, p1, p2, …, pn (pi ≤ 100), which is the profit that each task may bring to Aggie.

Output

For each test case, output a single number which is the largest profits that Aggie may gain.

Sample Input

1

5

3 4 5 1 2

1 1 1 2 2

Sample Output

4

样例dp数组中存的东西   

3

3 4

3 4 5

1 1  3

1 1  2 2

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#define eps 1e-8
#define ll long long
const int inf = 0x3f3f3f3f;
const long long mod=1e9+7;
const int N=100000+20;
using namespace std;
int t,n;
int a[N];
int b[N];
int dp[100*N];
using namespace std;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(dp,inf,sizeof(dp));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&b[i]);
        int len=0;//最大权值
        for(int i=0;i<n;i++)
        {
            int p=lower_bound(dp,dp+len,a[i])-dp;;
            for(int j=p;j<p+b[i];j++)
            {
                dp[j]=a[i];
                if(j==len) len++;
            }
        }
        printf("%d\n",len);
    }
}