衡阳市八中day1.docx

Nc有一个小小的愿望,能够帮kiko过一个有意义的生日,但是由于资金不够,Nc必须自己想办法赚money。想了很久,Nc决定卖花赚钱。现在Nc有n种漂亮的花,每种花各有ai盆,需要销往n个不同的城市,且每一种花只能销往一个地方,一个地方只能销售一种花。第i个城市距离Nc所在地为di公里,每一种花在第i个城市的卖价为vi,现在Nc需要将n种花分别运往n个不同的城市销售,每公里每盆花的运费为t。现在Nc想知道怎样销售才能赚最多的钱。输入文件 第一行两个整数n,t如题所述 第二行n个整数ai,表示第i种花的盆数 第三行n个整数di,表示第i个城市的距离 第四行n个整数vi,表示每种花在第i个城市的价格输出文件只有一行,n个整数,第i个数ci表示第i种花销往第ci个城市样例输入 31102015102030507060样例输出321Hint 第1种花销往第3座城市 第2种花销往第2座城市 第3种花销往第1座城市一共赚到10*60+20*70+15*50-30*10-20*20-10*15钱数据规模和约定 20%的数据n<=10 40%的数据n<=100 100%的数据n<=1000,1<=t,ai,di,vi<=10^9庆祝生日问题描述 很快就到了kiko的生日,Nc为了帮kiko庆祝生日,带着kiko出去玩,kiko拉着nc来到了游乐园。 “nc,nc~,那边好热闹,我们过去看看好不好”,“嗯”,kiko就拉着Nc往前走。Kiko拉着Nc走到一个神奇的屋子里,屋子里响起一位怪蜀黍的声音“欢迎来到地鼠之家,我们来玩个游戏吧”,Nc和kiko觉得会很好玩就答应了,怪蜀黍继续说“这是一个特殊的打地鼠游戏,你们面前有一块n*n的区域,每个地鼠会从这个区域内冒出一个单位时间,你们需要将地鼠踩下去,在时刻0的时候你们可以站在任意位置。游戏开始之后,你们可以移动,但是只能走直线,直线上的所有地鼠都会被踩到,我会告诉你们m只地鼠出来的时间和位置,然后根据你们踩的地鼠的数量多少,来给你们相应的奖励。对了,还有一点,你们可以走出区域外,但是必须走到整点上“因为今天是kiko的生日,所以Nc想踩更多的地鼠,以将最好的奖励送给kiko,让kiko高兴高兴。已知Nc每单位时间的移动距离<=d,现在Nc想知道他最多能踩多少只地鼠,你能帮助他么。输入文件 有多组数据请做到000结束,对于每组数据,格式如下: 第一行为n,d,m三个整数,如题所述 接下来m行每行x,y,t三个整数,表示在时刻t的时候,在(x,y)有一只地鼠冒出(0<=x,y<=n,1<=t<=10).输出文件 对于每组数据,输出一行一个整数ans,表示最多能踩中几只地鼠输入样例5430011212412054101011052162426001313012022102202000输出样例244 Hint 第一组数据,时刻0,站在(1,2)上时刻1,走到(2,4)上 第二组数据,时刻0,站在(1,0)上时刻1,走到(-2,3)