Jan 092009

ZJU 3077 – Move to Baggage Office

There are N item to be moved and you have initial strength S. Each item has three properties, vi – the value of this item, ai – the strength cost to move this item, bi – the strength you will regain after moving this item. Your strength should be at least ai to move the ith item.

You maybe unable to move all items, so you want to find the maximum value that you can gain.

Continue reading »

Jan 092009

ZJU 3075 – Ticket

You want to plan a training camp for your team in an N-days vacation (3 ≤ N ≤ 100000). The team must arrive at the camp before the first training day, and they may go home after the last training day. The training should be between P and Q days long, inclusive.

You decide to buy air tickets for all the team members. The price of air ticket in ith day is Ai. If the team arrive at the ith day and go back home at jth day, you need to pay Ai + Aj. You notice that sometimes the cost will be lower if they arrive earlier or back home later (the team may have free days). For each free day, you should pay F for their extra lunch fee.

Find the minimal total cost, including air tickets and extra lunch fee.

Continue reading »

Nov 252008

ZJU 3060 – Evil Game

You are given an M * N grids (1 <= M, N <= 100). You start from the most left-top cell (0, 0) and want to get to the most right-bottom cell (M-1, N-1). At any time, you can only move to left, right or down. Each cell (mij) contains an integer between -100 and 100 (inclusive) denoting the value that you will received when you visit the corresponding cell, in such manners:

  • mij = mij for the first visit to cell (i, j)
  • mij = -|mij| for each next visit to cell (i, j)

Calculate the maximum value that can be achieved to reach cell (M-1, N-1)!

Continue reading »