zrj2012-A3-0008

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：有N个城市，一个赏金猎人从城市1，依次走到城市N（1,2,3......n的顺序）。他初始有一定的金钱和攻击力。每到达一个城市，他可以先去用钱提升攻击力，然后去做任务，获得与攻击力成正比的金钱。第i个城市，如果他花c的钱，可以提升c/ai的攻击力；如果他做任务时，攻击力为x，他可以得到bi*x的钱。问他离开城市N时，最多能有多少钱。
这是我的题，直接把我当初的写的算法贴过来了。大家也可以去看[wiki:2012-0008 Bounty hunter]
首先可以明确的是，由于花钱提升攻击力可以是以任意实数进行的，钱的数目不影响城市的优劣性，并且每一处提升攻击力必然是把所有的钱都投入。然后我们定义在城市i，攻击力的单价是a[i]，之后得到钱的系数是b[i]，s[i]=b[1]+b[2]+...+b[i-1]，s[n+1]=b[1]+...+b[n] 再定义对于i<j， 城市i比城市j更优表示先在城市i提升攻击力在去j提升，比在i不提升等到j提升要优城市j比城市i更优表示在i不提升等到j提升，比先在城市i提升攻击力在去j提升要优 
1、对于城市i，假设花了c的钱提升攻击力，那么到城市k之前，通过这部分提升的攻击力可以得到的额外金钱是c/a[i]*(s[k]-s[i])。 
2、令s[n+2]=+∞，设j是最小的满足c/a[i]*(s[j]-s[i])>=c的正整数，即到达城市j之前，我刚刚可以通过额外提升的攻击力得到比投入更多的钱。（j=n+1表示旅程结束之时）显然，对于任意城市k>=j，i比k更优（因为这样到k时再有更多的钱的同时攻击力更高了）因此我们接着考虑i+1~j-1的城市 
3、考虑城市i<k<j，如果j比k优，k比i优，那么j比i优，因此我们只需要考虑在i之后那个最优的城市ii即可。（从最优队列的顶部取得） 
4、若ii>=j,i比ii优，把i加入最优队列。若i<ii<j。由于ii比任意k>i都要优，因此在i+1~ii-1之间的城市，我们都不需要去提升攻击力。 
因此我们只有两种策略： 
①在i提升攻击力，然后在ii提升攻击力。 
②只在ii提升攻击力。 
这两种策略，在ii提升完毕攻击力（还没有获得金钱）之后，只剩下攻击力一个指数。因此我们只需要通过比较两者的攻击力就可以知道哪个更优。若i比ii优，则把i加入最优队列。 
最后只在最优队列提升攻击力，模拟一边就好了。

题目大意：有N个城市，一个赏金猎人从城市1，依次走到城市N（1,2,3......n的顺序）。他初始有一定的金钱和攻击力。每到达一个城市，他可以先去用钱提升攻击力，然后去做任务，获得与攻击力成正比的金钱。第i个城市，如果他花c的钱，可以提升c/ai的攻击力；如果他做任务时，攻击力为x，他可以得到bi*x的钱。问他离开城市N时，最多能有多少钱。

这是我的题，直接把我当初的写的算法贴过来了。大家也可以去看Bounty hunter

首先可以明确的是，由于花钱提升攻击力可以是以任意实数进行的，钱的数目不影响城市的优劣性，并且每一处提升攻击力必然是把所有的钱都投入。然后我们定义在城市i，攻击力的单价是a[i]，之后得到钱的系数是b[i]，s[i]=b[1]+b[2]+...+b[i-1]，s[n+1]=b[1]+...+b[n] 再定义对于i

1、对于城市i，假设花了c的钱提升攻击力，那么到城市k之前，通过这部分提升的攻击力可以得到的额外金钱是c/a[i]*(s[k]-s[i])。

2、令s[n+2]=+∞，设j是最小的满足c/a[i]*(s[j]-s[i])>=c的正整数，即到达城市j之前，我刚刚可以通过额外提升的攻击力得到比投入更多的钱。（j=n+1表示旅程结束之时）显然，对于任意城市k>=j，i比k更优（因为这样到k时再有更多的钱的同时攻击力更高了）因此我们接着考虑i+1~j-1的城市

3、考虑城市i

4、若ii>=j,i比ii优，把i加入最优队列。若ii都要优，因此在i+1~ii-1之间的城市，我们都不需要去提升攻击力。

因此我们只有两种策略：

①在i提升攻击力，然后在ii提升攻击力。

②只在ii提升攻击力。

这两种策略，在ii提升完毕攻击力（还没有获得金钱）之后，只剩下攻击力一个指数。因此我们只需要通过比较两者的攻击力就可以知道哪个更优。若i比ii优，则把i加入最优队列。

最后只在最优队列提升攻击力，模拟一边就好了。