Processing math: 100%

A dp problem(I think)

Revision en10, by SkyMagic, 2024-11-25 10:42:25

The problem is basically monopoly but you don't need to roll dices or stuffs, we have N (1N105) positions each of which are all empty. We can play any number of rounds by each rounds we choose an index i, if it's empty, we'll build a house on that position which will cost us Ai, and gives us 1 points, but if it's a house already, we'll transform the house to a apartment, which will cost us Bi, and gives us 1 points, if it's already an apartment we'll do nothing, which gives us nothing and cost us nothing (so there's no reason to do this). We always want to maximize the amount of points. (We can make an apartment on the position i if and only if the position i is a already a house)

There will be Q (1Q105) queries, on the ith query (1iQ) we have a budget of Xi, which means that the total sums of cost cannot exceed Xi. We want to know that, for each queries i (1iQ) what is the maximum amount of points we can possibly get?

Constraints:

  • 1N,Q105

  • 1Ai,Bi109

  • 1Xi21014

What I tried(Not the full solution)

I could not find a solution. But if anyone can, please comment what the solution to this problem could be(Other people would know too!), I would really appreciate it!

Thanks in advance!

Tags problem, optimization, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English SkyMagic 2024-11-25 10:42:25 3 Tiny change: ' \leq 10^{14}$\n\n- $1' -> ' \leq 10^{9}$\n\n- $1'
en9 English SkyMagic 2024-11-24 16:06:16 26
en8 English SkyMagic 2024-11-24 14:23:26 1705 (published)
en7 English SkyMagic 2024-11-24 14:21:59 295
en6 English SkyMagic 2024-11-24 14:16:26 389
en5 English SkyMagic 2024-11-24 14:10:01 6
en4 English SkyMagic 2024-11-24 14:09:51 259
en3 English SkyMagic 2024-11-24 14:07:06 2 Tiny change: 'e $Q$ $(1 leq Q leq 10^5)$' -> 'e $Q$ $(1 \leq Q \leq 10^5)$'
en2 English SkyMagic 2024-11-24 14:05:50 464
en1 English SkyMagic 2024-11-24 13:57:26 451 Initial revision (saved to drafts)