TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1996
  • 题目
  • P1996【DP】魅力花园
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    在城市里会有很多花园,我们如何判断某一个花园是不是魅力花园呢?不同的人有不同的要求,而且花园对于不同的人的要求的敏感程度不同。比如市长的要求要比市民的要求有用的多,城管的要求又高于市长的要求。花园的园长很为难。他必须让尽可能多的人都感到满意。
    假设有n个群体对花园提出了n个要求,每个群体的要求不同,园长根据要求被提出的时间先后和要求的价值大小进行选择性的满足。园长只会对时间早的和价值高的要求进行满足。例如两个要求A和B的提出时间分别是a, b(a<b),价值分别是a′,b′(a′>b′),那么他们可以同时被满足。
    园长为了打造魅力花园,当然希望满足尽可能多的不同群体的要求。他想让你帮他设计一个规划,计算出最多能满足多少个群体的要求。

    输入格式

    第一行一个n,表示有n个群体;
    第二行n个整数,n个群体的问题的时间由早到晚排序后的标号顺序;
    第三行n个整数,n个群体的问题的价值从大到小排序后的标号顺序;

    输出格式

    一个数表示最多能满足的要求数;

    样例输入

    5
    1 3 4 5 6
    6 5 3 4 1

    样例输出

    2

    提示

    30%的数据:1≤n≤1000;
    100%的数据:1≤n≤100000;