Problem - 808E - Codeforces題意： 有 N 個物品，你的背包容量為 M。第 i 個物品容量為 W[ i ]，價值為 C[ i ]。求可容的最大可能價值總和。制約： 1 ≤ N ≤ 1e5 1 ≤ M ≤ 3e5 1 ≤ W[ i ] ≤ 3 1 ≤ C[ i ] ≤ 1e9解法： 如果只有兩種重量，那有多簡單。 考慮討…

Problem - F - Codeforces題意： 有 N 隻老鼠，用座標描述。有 M 個洞，用座標和容量描述。一隻位於座標 x 的老鼠進到位於座標 y 的洞裡要花費 abs( x - y )。問最小花費總和為何，才能使所有老鼠進洞。制約： 1 ≤ N, M ≤ 5000 abs( X[ i ] ), abs( P[ i ] )…

No.409 ダイエット - yukicoder題意： 有 N 天，第 i 天有重量 D[ i ] 單位的甜甜圈可以吃。你現在的重量是 W 單位，你想減肥，所以每天你可以選擇吃或不吃。如果吃了，你的體重就會增加吃掉的重量並歸零壓力值，否則你會減去 A 單位的重量但同時增加一個單…

F: Dam - AtCoder Regular Contest 072 | AtCoder題意： 有一個水壩，容量是 L。有 N 天，第 i 天早上會有溫度 T[ i ] 容量 V[ i ] 的水流進水壩，晚上你可以讓水壩流出任意適當多容量的水。分別對於 [ 1, N ] 的所有 i，問使得第 i 天恰有容量 L 的水在水壩…

Problem - B - Codeforces題意： 你有 n 個 PhOI 獎牌，m 個 IOI 獎牌，各自用價值 c 和重量 w 描述。你有一個容器可以容下不超過 d 的總重量，問在兩種獎牌至少各一枚，且當一種獎牌中價值為 x 的獎牌被納入則所有價值超過 x 的同種獎牌也都必須納入的前提…

No.489 株に挑戦 - yukicoder題意： 買賣股票，買跟麥只做一次。必須滿足買的日期 i 和賣的日期 j 有 j - i 制約： 2 ≤ N ≤ 1e5 1 ≤ D 1 ≤ K ≤ 1e6 1 ≤ xi ≤ 1e6解法： 努力寫了一次線段樹，但 python 也很給力的 TLE 了。 經典的滑動視窗： window[ i ]: i …

Problem - E - Codeforces題意： 給一個矩陣，表示每對人之間的憎恨值。現在要把人划分為 K 群，每群必須都是連續編號的人。一個群的憎恨值貢獻是所有編號的有序對的憎恨值總和。求最少憎恨值總和。資料規模： The first line contains two integers n and k…

Problem Description: There are N shops that sell potions, and each of them only sells one kind of potion. The i'th shop sells potions for P[ i ] per glass, where each glass could heal B[ i ] units of health, but has only C[ i ] glasses in …

1180 -- Batch Scheduling題意： 有 N 個工作，用 T[ i ], F[ i ] 描述第 i 個工作需要花費的時間，以及單位時間的價值。第 i + 1 個工作不能在第 i 個工作完成之前被完成。每次可以選擇 k 個，未完成的工作中編號最小的工作，花費其 T 的總和，令之 P，的時…

Problem - B - Codeforces題意： 給你 n 個數組成的數列 a，和總和上限 s，長度下限 l。求將數列 a 分割成最少數量的連續片段，滿足每個片段總和不超過 s，長度不小於 l。求最少可能片段數量。資料規模： 1 ≤ n ≤ 1e5, 0 ≤ s ≤ 1e9, 1 ≤ l ≤ 1e5,- 1e9 ≤ ai …

Problem - D - Codeforces題意： 給一棵樹，有點權和邊權。定義 f( v, u ) 為真，若 u 為 v 的子樹裡的節點，且 dis( u, v ) ≤ 邊權[ u ]。對樹上所有節點 x，求 SIGMA( f( x, y ) | ALL y )。資料規模： 節點數 1 ≤ n ≤ 2e5 點權 1 ≤ a[ i ]≤ 1e9 邊權 1 ≤ …

1063 - 最大矩形(Area) | TIOJ INFOR Online Judge 跟這題很像的，不過這次是要求矩形面積。 UVA 12265 Selling Land ( Stack Monotonicity ) - 0w1 很容易注意到，如果先發生的( 左邊開始的 )矩形比後發生的矩形高，那只要先發生的矩形好好的，後面發生的矩…

UVa Online Judge 白訓練指南的一道經典的單調棧好題。思路是先想像我們大致會做一個高度單調遞增的維護，注意到要判斷一個左上角到當前的右下角構成的矩形周長是否足夠優，只需要知道它的高和當前的列的差( 寬 )。由於只有寬是動態增加的，所以只要能不斷的…

Problem - E - Codeforces Basically when the car is in gas station i, there is one and only one optimal decision. If it is possible to move to the first station with cheaper gas price after this one, buy the minimum amount of gas here in or…

http://sprout.tw/oj/pro/144/ Short summary for the problem: given an array of N ≤ 1000 numbers a[ 1 ], a[ 2 ] .., a[ N ], each pair of numbers a[ i ], a[ i + 1 ]adjacent to each other can merge into a new single number, producing a[ i ] + …

This optimization is also called "Convex Hull Trick" because it is either maintaining an upper convex hull ( decreasing slopes ) or a lower convex hull. Also note that there are problems that do not necessarily have to be monotonous but st…

A deque ( double ended queue ) is a data structure that supports push/ pop from both ends with constant time complexity. It can be used to optimize algorithms that deal with monotonous properties. The first time I saw this data structure, …

Stacks can be used to maintain for monotonous properties, can optimize for many problems, but only if you can discover the monotony in the problem. Here are some problems for exercise from the ant book. 3250 -- Bad Hair Day POJ 3250 Bad Ha…