(translation available later)
low = mid; //提高下边界
high = mid - 1； //降低上边界
这样的话如果用 mid = (high + low)/2; 上下取整的话。如果low = 2， high = 3
如果mid = 2 满足条件那么就会一直死循环。
这是因为low = mid不修改本身。
因此要用向上取证 mid = (high + low + 1)/2; 这样的话不会出现问题了。
high = mid; //降低上边界
low = mid + 1； //提高下边界
这样的话mid = (high + low + 1)/2;
对于 low = 2, high = 3如果mid = 2 满足条件就会出现死循环了。
因此必须 mid = (high + low)/2;
总结下来就是，如果边界变动过程中满足条件后low = mid， 那么我们要对mid向上取整使得连续两次的low的值不会相同，
对于 high = mid，那么我们要对mid向下取整使得连续两次的high的值不同。
POJ 1157 / IOI 1999: Little Shop of Flowers
The phrase "select ... from ... so that ..." tells that this is a DP problem. Since there are only two incrementable variables (flowers and pots), the DP array is 2-D. Therefore, DP[i][j] must stand for the maximum pleaseantness with I flowers and J pots. Since this problem requires the result to be based on both the DP array and the input together we can merge them into one array. Also, since every value D[i][j] where j
Problem: 08 Clock
What's the problem?
One optimization is not always enough. Other checks, as simple as drawing three branches for each nodes, can reveal that doing step 2 after step 1 and doing step 1 after step 2 is the same; with this, you can remove four out of nine nodes per round, a significant optimization than the little 1/729 improvement through detecting repeated steps. It is very simple to just do some more work extending the bounds to revealanother more important optimization.
This problem uses a BFS search for the shortest-reachable solution. However, a simple BFS is way too slow. But we can still improve the O(9^n) time complexity. We can first save each state as a base-4 number (e.g. 132331201) and convert it into base 10, then save it to a hash array. Or even more simply, we can realize that a move sequence like "I J" where I and J are integers in 1~9 produces the same result as the sequence "J I", cutting down 4/9 values every round. Also, storing the different movements can be done in an array: store a 0 or 1 in the array depending on whether or not a move changes that clock. Then, iterating over a specific sub-array and adding the value, whether 0 or 1, updates the array.