F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

LIS

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 207    Accepted Submission(s): 85


Problem Description
给定长度为 $n$ 的排列 $a$,删除 $a_i$ 的代价是 $b_i$。

现在希望删除一些 $a_i$,使得删完后 $a$ 的 LIS(最长上升子序列)长度 $\le k$,最小化被删除元素的代价和。

对 $1 \le k \le n$ 分别求出答案。
 

Input
本题有多组数据。第一行一个正整数 $T$($1\le T\le5$),表示测试数据组数。

对于每组数据,第一行一个整数 $n$($1 \le n \le 500$)。

第二行 $n$ 个整数 $a_1 \sim a_n$($1 \le a_i \le n$,$a_i$ 互不相同)。

第三行 $n$ 个整数 $b_1 \sim b_n$($1 \le b_i \le 10^6$)。
 

Output
对于每组数据,输出一行 $n$ 个整数,第 $i$ 个整数表示 $k=i$ 时的最小代价和。
 

Sample Input
4 5 3 1 4 2 5 6 7 10 2 4 6 2 1 5 6 4 3 8 7 9 7 5 10 6 1 3 2 5 6 4 2 10 2 10 8 2 5 1 2 3 4 5 5 4 3 2 1
 

Sample Output
16 4 0 0 0 22 7 0 0 0 0 22 10 2 0 0 0 10 6 3 1 0
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-22 15:49:22, Gzip enabled