bzoj1049: [HAOI2006]数字序列
设F[i]为以i开头的最长上升序列的长度,第一个元素A[i]必须满足F[i]>=M,第x个元素为A[y]，则第(x+1)个元素A[z]需要满足的条件是A[z]>A[y]，且F[z]=F[y]-1
这位的题解很详细 http://www.cppblog.com/MatoNo1/archive/2012/09/08/189969.html
const int N = 35010;struct Edge {int To;Edge *Next;Edge() {Next = NULL, To = -1;}Edge(int _To, Edge *_Next) : To(_To), Next(_Next) {}} *Fir[N];int n, Data[N];int Dp[N], F[N];inline void Input() {scanf("%d", &n);For(i, 1, n) scanf("%d", &Data[i]), Data[i] -= i;}int T[N], Len; // Step1LL C1[N], C2[N]; // Step2inline void Ins(int u, int v) {Fir[u] = new Edge(v, Fir[u]);}inline void Solve() {// Step1T[Len = 0] = -INF, Data[++n] = INF;For(i, 1, n) {int x = upper_bound(T, T + Len + 1, Data[i]) - T;Len = max(Len, x), Dp[i] = x, T[x] = Data[i];}printf("%d\n", n - Dp[n]);Data[0] = -INF, Dp[0] = 0;// Step2For(i, 0, n) Fir[i] = NULL;Ford(i, n, 0) Ins(Dp[i], i), F[i] = INF;F[0] = 0;For(i, 1, n)for(Edge *Tab = Fir[Dp[i] - 1]; Tab != NULL; Tab = Tab->Next) {int v = Tab->To;if(v > i) break;if(Data[v] > Data[i]) continue;For(k, v, i) C1[k] = abs(Data[k] - Data[v]), C2[k] = abs(Data[k] - Data[i]);For(k, v + 1, i) C1[k] += C1[k - 1], C2[k] += C2[k - 1];For(k, v, i - 1) F[i] = min(F[i], F[v] + C1[k] - C1[v] + C2[i] - C2[k]);}printf("%d\n", F[n]);// debug//For(i, 1, n) printf("%d ", F[i]);} int main() { #ifndef ONLINE_JUDGE SETIO("1049"); #endif Input(); Solve(); return 0;}?