c271: 疊疊樂(Easy)
Tags : dp sortings
Accepted rate : 9人/12人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-08-18 13:16

Content

你會得到一堆箱子,每個箱子有各自的重量,以及負重

每個箱子等高等寬但有些不一樣長

我們希望可以疊很多箱子,而且長度由下而上是非遞增的

當箱子包含自身以上的箱子總重超過負重,箱子就會壞掉

 

關於負重的補充,{}左至右相當於上到下放置箱子

Example #1:

箱子重量{2, 4, 8}, 所需負重(2, 6, 14)

Example #2:

箱子重量{2, 2, 3}, 所需負重(2, 4, 7)

Input

第一行包含整數T,代表有T筆小測資

每筆小測資中,第一行包含整數N(1≤N≤1000),接下來N行包含Wi,Si,L(1≤Wi,Si,L≤109 ),分別代表重量,負重,長度

Output

對於每一筆小測資,輸出最多可以疊幾個箱子

 

Sample Input
2
2
2 4 2
8 10 3
2
2 4 2
8 9 3
Sample Output
2
1
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (12%): 1.0s , <1K
不公開 測資點#1 (12%): 1.0s , <1M
不公開 測資點#2 (12%): 1.0s , <1M
不公開 測資點#3 (12%): 1.0s , <1M
不公開 測資點#4 (13%): 1.0s , <1M
不公開 測資點#5 (13%): 1.0s , <10M
不公開 測資點#6 (13%): 1.0s , <10M
不公開 測資點#7 (13%): 1.0s , <1K
Hint :

19/08/18 題目有誤,大幅度變動

 

測資#0: T=10,N=10, 1≤ Wi ,Si≤ 100,1≤ L≤10

測資#1: T=10,N=1000, 1≤ Wi ,Si≤ 100,1≤ L≤10

測資#2: T=10,N=1000, 1≤ Wi ,Si, L≤ 106

測資#3: T=10,N=1000, 1≤ Wi, Si ≤ 106 ,1 ≤ L≤ 10

測資#4: T=100,N=100,1≤ Wi, Si ≤ 106 ,1 ≤ L≤ 10

測資#5: T=100,N=1000,1≤ Wi, Si ≤ 109 ,1 ≤ L≤ 10

測資#6: T=100,N=1000,1≤ Wi, Si ≤ 109 ,1 ≤ L≤ 10

測資#7: T=5,1 ≤ N, Wi, Si, L≤ 10

Tags:
dp sortings
出處:
106學年度板橋高中校內資訊學科能力競賽310573sao [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」