问题描述：已知数组a以及若干个查询(x, y)，求a[x~y]之间的最小值。
分析
不难发现：若取t使得$2^t\leq y-x+1$且$2^{t+1}>y-x+1$，则有：
$$[x, x+t]\bigcup[y-t+1,y]=[x,y]$$
运用二进制的思想，我们只需预处理出$i~i+2^k-1$之间的最小值，即可快速完成查询。设dp[i][j]为$i~i+2^j-1$之间的最小值，则有：
$$dp[i][j]=min(dp[i][j-1],dp[i+2^{j-1}][j-1])$$。
Code
var
a: array [1..100000] of longint;
dp: array [1..1000
继续阅读 »
下面介绍一下 Android 5.0 官方推出了一个全新的标签 vector --> 官网地址
创建矢量图片
在 Android 5.0（API 级别 21）及更高版本中，您可定义矢量图片，而且图片可在不丢失定义的情况下缩放。您只需一个资产文件即可创建一个矢量图像，而位图图像则需要为每个屏幕密度提供一个资产文件。如果要创建一个矢量图像，请您在 XML 元素中定义形状的详情。
下列示例以心形定义一个矢量图像：
```xml
android:height="256dp"
android:width="256dp"
android:viewportWidth="32"
androi
继续阅读 »
I have trained my algorithm on leetcode a period of time.
Today, I will explain my solution about Minimum Height Trees.
My solution beat ~95% against others but it is hard to explain what is I do.
Please allow me to introduce the solution from easy to hard. If you only need the
last solution, jump to
继续阅读 »
这是一道区间型DP，转移方程很简单，但在实现的过程中却遇见了很多坑，在此记录一下。 链接：Link 耗时：0.368s
容易想到，前i个数的划分情况可以由1,2,3...,i-1的划分情况来决定。因此很容易得到状态转移方程：
d[i] = min(d[i], d[j]+1) //j = 0, 1, 2...n-1 并且 s[j+1, i]为回文串，初始条件：d[i] = i。
d[i]表示前i项的最小划分。这样一来状态转移的复杂度就为O($n^2$)。
但状态转移的判断呢？“回文串”是一个复杂的条件，判断一个串是否为回文串需要将该串至少遍历一遍。这样一来时间复杂度就上升为O($n^3$)了。而事实上在这种算法中有许多无谓的计
继续阅读 »