MMAXPER - Rectangles Perimeter


Cho n hình chữ nhật đánh số từ 1 đến n, các hình chữ nhật này được đặt 
tiếp xúc với trục OX và nằm kề nhau từ trái qua phải theo thứ tự chỉ số
Mỗi hình chữ nhật có thể tiếp xúc với trục Ox theo bất kỳ cạnh cạnh (xem hình). 
Cần tính độ dài lớn nhất của đường gấp phía trên (xem hình) 
Image and video hosting by TinyPic

INPUT

Dòng đầu tiên ghi số hình chữ nhật n, n dòng tiếp theo mỗi dòng ghi 
hai số a_i  và b_i, độ dài cạnh của hình chữ nhật thứ i.
Ràng buộc : 0 < n < 1000; 0 < a_i < b_i < 1000, với i = 1, 2, …, n. 

Ví dụ:
5 
2 5 
3 8 
1 10 
7 14 
2 5 

OUTPUT

Ghi ra độ dài lớn nhất tìm được 

Ví dụ: 

68
Giải thích
Cách xếp mà thu được chiều dài lớn nhất là hình trên. Cạnh phía 
trên gồm các đoạn  DC, CG, GF, FJ,  JI,  IM, ML, LP,  và PO. 
Độ dài của đoạn này là 5 + 6 + 3 + 7 + 10 + 13 + 7 + 12 + 5 = 68
Problem for kid - Please, think like kid.

hide comments
dendrite5460: 2019-01-18 13:03:44

bottom up dp works :)

ankitpriyarup: 2018-12-22 17:04:56

AC in one go :) Simple

ankit1cool: 2018-06-21 12:58:04

I solved it using top-down but i don't understand what is the meaning of "Problem for kid - Please, think like kid." does it mean that it has a non dp solution

akash13s: 2018-05-23 18:43:30

Nice problem:)

vivek_rathi: 2018-04-01 10:14:02

"Problem for kid - Please, think like kid." Mind these words

sahil070197: 2018-03-10 10:35:47

@mohit_aggarwal I support you! pagal bna rha hai @infernodragon

mohit_aggarwal: 2018-02-28 12:44:41

@infernodragon
Values are well within the range !!
Don't mislead Others !!
BTW AC in One go ;-)

up79: 2017-06-04 07:41:15

a must do problem on DP :)
learnt something new :D

da_201501181: 2017-05-09 12:59:41

Worth to be attempted for beginners..!!

siddharth_0196: 2016-10-08 15:33:45

Bottom-Up works just fine! :D


Added by:~!(*(@*!@^&
Date:2009-02-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:BOI For Kid 08