icontofig | 发布于 2017-01-18 09:08:42 | 阅读量 91 | CDQ分治 DP
发布于 2017-01-18 09:08:42 | CDQ分治 DP
NOI2007 货币兑换 Cash 【CDQ分治 斜率优化DP】
Description小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A纪念券(以下简称A券)和 B纪念券(以下简称B券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券 和 B券 的价值分别为 AK 和 BK(元/单位金券)。为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。比例交易法分为两个方面:(a)卖出金券:顾客提供一个[0,100] 内的实数 OP 作为卖出比例,其意义为:将 OP% 的 A券和 OP% 的 B券 以当时
继续阅读
icontofig | 发布于 2017-01-18 08:56:15 | 阅读量 204 | CDQ分治 树状数组
发布于 2017-01-18 08:56:15 | CDQ分治 树状数组
Description你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:命令 参数限制 内容1 x y A 1<=x,y<=N,A是正整数 将格子x,y里的数字加上A2 x1 y1 x2 y2 1<=x1<= x2<=N1<=y1<= y2<=N 输出x1 y1 x2 y2这个矩形内的数字和3 无 终止程序 Input输入文件第一行一个正整数N。 接下来每行一个操作。 Output对于每个2操作,输出一个对应的答案。 Sample Input41 2 3 32 1 1 3 31 2 2 22 2 2 3 43
继续阅读