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; // Step1
LL C1[N], C2[N]; // Step2
inline void Ins(int u, int v) {
	Fir[u] = new Edge(v, Fir[u]);
}
inline void Solve() {
	// Step1
	T[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;
	
	// Step2
	For(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;
}