题目描述

这一天，有一列车子排起了一排长队，必经之路是一个被魔王笼罩的山洞。每辆车 的司机害怕魔王程度不同，所以每个司机有一些要求。 　　车子有n台，排成一条长队，每辆车有4个属性: 　　V ——这辆车的总价值，价值就是比如它其中的乘客和货物的价值 　　c ——这辆车里面的人数量（司机表示自己也算一个乘客，司机和乘客不用区分开来） 　　l ——在这辆车的前面需要总量正好为多少乘客的车（不多也不少），这车才敢开 　　r ——在这辆车的后面需要总量正好为多少乘客的车（不多也不少），这车才敢开 　　“前面需要总量正好为多少乘客的车”指的是驶在这辆车前面所有的车的乘客总数。 　　“后面需要总量正好为多少乘客的车”指的是驶在这辆车后面所有的车的乘客总数。 　　你不能改变每辆车在车队的相对顺序，但你可以安排某些车退出车队，保证依然在 车队的每辆车都敢开了，即满足上述条件，并且剩下车的v的总量最大。 　　----------------------------- 　　简单来说，给您按输入顺序排列的n辆车，您需要删去里面的一些车（剩下的车仍然 按原相对顺序排列）。 　　使得对于每辆车，若它没被删去，设其为输入的第i辆车， 　　要满足 　　l[i]= sigma{c[j] | ji 且第j辆车没被删去} 　　在满足这些条件前提下，要求sigma{V[i] | i没被删去} 最大， 　　请输出这个最大值，并且递增输出没有被删去的车的标号。 输入格式 　　输入的第一行为一个正整数n（1<=n<=10^5）——车的个数。 　　接下来n行，每行四个整数，第i行的数字: vi, ci,li ,ri ,（1<=vi<=10^4 , 1<=ci<=10^5,0<=li,ri<=10^5），车子们从1开始编号，从车队的最前头开始算起。 输出格式 　　第一行输出一个数k：会继续在这车队里的车的总数（注意我们的目标是让价值最大 ）。 　　第二行k个数，递增输出继续在车队里的车的编号。 　　请留心你不允许改变车的次序。如果答案不唯一，输出任意一个。 样例输入 5 1 1 0 3 1 1 1 2 1 1 2 1 1 1 3 0 2 1 3 0 样例输出 4 1 2 3 5 样例输入 5 1 1 0 3 10 1 2 1 2 2 1 1 10 1 1 2 3 1 3 0 样例输出 3 1 3 5 数据规模和约定 　　对于20%的数据，n<=100 　　对于50%的数据，n<=1000 　　对于100%的数据，n<=100000 　　对于100%的数据，1<=vi<=10^4 , 1<=ci<=10^5,0<=li,ri<=10^5

输入格式

输入的第一行为一个正整数n（1<=n<=10^5）——车的个数。 　　接下来n行，每行四个整数，第i行的数字: vi, ci,li ,ri ,（1<=vi<=10^4 , 1<=ci<=10^5,0<=li,ri<=10^5），车子们从1开始编号，从车队的最前头开始算起。 输出格式 　　第一行输出一个数k：会继续在这车队里的车的总数（注意我们的目标是让价值最大 ）。 　　第二行k个数，递增输出继续在车队里的车的编号。 　　请留心你不允许改变车的次序。如果答案不唯一，输出任意一个。 样例输入 5 1 1 0 3 1 1 1 2 1 1 2 1 1 1 3 0 2 1 3 0 样例输出 4 1 2 3 5 样例输入 5 1 1 0 3 10 1 2 1 2 2 1 1 10 1 1 2 3 1 3 0 样例输出 3 1 3 5 数据规模和约定 　　对于20%的数据，n<=100 　　对于50%的数据，n<=1000 　　对于100%的数据，n<=100000 　　对于100%的数据，1<=vi<=10^4 , 1<=ci<=10^5,0<=li,ri<=10^5

输出格式

第一行输出一个数k：会继续在这车队里的车的总数（注意我们的目标是让价值最大 ）。 　　第二行k个数，递增输出继续在车队里的车的编号。 　　请留心你不允许改变车的次序。如果答案不唯一，输出任意一个。 样例输入 5 1 1 0 3 1 1 1 2 1 1 2 1 1 1 3 0 2 1 3 0 样例输出 4 1 2 3 5 样例输入 5 1 1 0 3 10 1 2 1 2 2 1 1 10 1 1 2 3 1 3 0 样例输出 3 1 3 5 数据规模和约定 　　对于20%的数据，n<=100 　　对于50%的数据，n<=1000 　　对于100%的数据，n<=100000 　　对于100%的数据，1<=vi<=10^4 , 1<=ci<=10^5,0<=li,ri<=10^5

5
1 1 0 3
1 1 1 2
1 1 2 1
1 1 3 0
2 1 3 0
样例输出
4
1 2 3 5
样例输入
5
1 1 0 3
10 1 2 1
2 2 1 1
10 1 1 2
3 1 3 0
样例输出
3
1 3 5
数据规模和约定
　　对于20%的数据，n<=100
　　对于50%的数据，n<=1000
　　对于100%的数据，n<=100000
　　对于100%的数据，1<=vi<=10^4 , 1<=ci<=10^5,0<=li,ri<=10^5

4
1 2 3 5
样例输入
5
1 1 0 3
10 1 2 1
2 2 1 1
10 1 1 2
3 1 3 0
样例输出
3
1 3 5
数据规模和约定
　　对于20%的数据，n<=100
　　对于50%的数据，n<=1000
　　对于100%的数据，n<=100000
　　对于100%的数据，1<=vi<=10^4 , 1<=ci<=10^5,0<=li,ri<=10^5

来源

蓝桥杯 算法训练