最近做了兩道LIS模型題，感覺到模型比較好，總結(jié)一下囧。
【1】
[HAOI2007]上升序列 預(yù)處理：設(shè)F[i]為以i開頭的最長(zhǎng)上升序列的長(zhǎng)度，怎么求不用說了吧囧……
假設(shè)目前需要求長(zhǎng)度為M的、標(biāo)號(hào)字典序最小的上升序列，顯然其第一個(gè)元素A[i]必須滿足F[i]>=M（注意，不是等于，是大于等于！），找到滿足這個(gè)條件的最小的i即可。然后，設(shè)目前已經(jīng)求出了該序列的第x個(gè)元素為A[y]，則第(x+1)個(gè)元素A[z]需要滿足的條件是A[z]>A[y]，且F[z]=F[y]-1，找到滿足這個(gè)條件的最小的z即為該序列的第(x+1)個(gè)元素。按照這種方法，掃描一遍就可以求出整個(gè)序列，時(shí)間復(fù)雜度為O(N)。如果整個(gè)序列的最長(zhǎng)上升序列長(zhǎng)度<M，則無解。
代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 10010, MAXM = 1010, INF = ~0U >> 2;
int n, m, len, A[MAXN], F[MAXN], D[MAXN], res[MAXM];
void prepare()
{
D[len = 0] = INF; int l, r, mid;
rre(i, n) if (A[i] < D[len]) D[F[i] = ++len] = A[i]; else {
l = 0; r = len;
while (l < r) {
mid = l + r + 1 >> 1;
if (A[i] < D[mid]) l = mid; else r = mid - 1;
}
F[i] = l + 1; D[l + 1] = A[i];
}
}
void solve()
{
int x, y;
re(i, n) if (F[i] >= m) {
res[0] = A[i]; if (m == 1) return; x = m - 1; y = 1;
re2(j, i+1, n) if (F[j] >= x && A[j] > res[y - 1]) {res[y++] = A[j]; if (y == m) return; else x--;}
}
}
int main()
{
scanf("%d", &n); re(i, n) scanf("%d", &A[i]);
prepare();
int m_s; scanf("%d", &m_s);
re(i, m_s) {scanf("%d", &m); if (m > len) puts("Impossible"); else {solve(); re(j, m-1) printf("%d ", res[j]); printf("%d\n", res[m - 1]);}}
return 0;
}
【2】
[HAOI2006]數(shù)字序列 首先，由于序列的所有元素都是整數(shù)，所以可以將原序列的所有元素減去它的下標(biāo)，這樣就把上升序列轉(zhuǎn)化為不下降序列了。
第一問的結(jié)果顯然就是(N-新序列的最長(zhǎng)不下降序列長(zhǎng)度)。關(guān)鍵在于第二問。以下A均表示新序列。
設(shè)F[i]為以A[i]結(jié)尾的最長(zhǎng)不下降序列長(zhǎng)度（同樣，求法不用說了），G[i]為在A[i]不修改的前提下將A[0..i]轉(zhuǎn)變?yōu)椴幌陆敌蛄械淖钚⌒薷牧俊Ｊ紫惹蟪鯢[i]，然后在求G[i]時(shí)，枚舉上一個(gè)“不動(dòng)點(diǎn)”（就是不修改的元素）A[j]（顯然必須滿足A[j]<=A[i]且F[j]=F[i]-1），這樣最小修改量就是G[j]+(將A[j..i]轉(zhuǎn)變?yōu)椴幌陆敌蛄械淖钚⌒薷牧浚？梢宰C明，A[j..i]的最優(yōu)修改方案必然是將A[j+1..t]全部修改為A[j]，A[t+1..i]全部修改為A[i]，這里t是一個(gè)[j..i]范圍的值。問題就是如何求出最優(yōu)的t？
一開始，假設(shè)t=j，即把A[j+1..i-1]全部修改為A[i]，計(jì)算出修改量，設(shè)為S。然后，由于A[j+1..i-1]之間的元素要么小于A[j]，要么大于A[i]（這個(gè)是顯然的囧），我們把小于A[j]的元素稱為“小數(shù)”，把大于A[i]的元素稱為“大數(shù)”，則當(dāng)t取t0時(shí)，修改量為S-(A[i]-A[j])*(A[j+1..t0]中的“小數(shù)”個(gè)數(shù)減去“大數(shù)”個(gè)數(shù)）。這樣，只需掃描一下，求出使得(A[j+1..t0]中的“小數(shù)”個(gè)數(shù)減去“大數(shù)”個(gè)數(shù)）值最大的t0即可。
當(dāng)然還有一個(gè)問題，對(duì)于同一個(gè)i，滿足“A[j]<=A[i]且F[j]=F[i]-1”的元素個(gè)數(shù)可能有很多，如果一個(gè)一個(gè)枚舉，一個(gè)一個(gè)掃描，會(huì)很慢的囧……解決方法是，求出滿足這個(gè)條件的j中最小的一個(gè)，設(shè)為j0，然后把A[j0+1..i-1]中的所有“小數(shù)”和“大數(shù)”全部處理出來，然后用類似前綴和的方法就能搞了囧……當(dāng)然，為了找到j(luò)0，需要建一個(gè)二分圖，邊為(F[i], i)。
最后，為了方便，可以把A序列的左邊加一個(gè)-INF，右邊加一個(gè)+INF。最后總的時(shí)間復(fù)雜度，理論上為O(N
2)，但由于是隨機(jī)數(shù)據(jù)，所以遠(yuǎn)遠(yuǎn)達(dá)不到這個(gè)級(jí)別。
代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 40010, INF = ~0U >> 2;
struct edge {
int a, b, pre, next;
} E[MAXN << 1];
int n, m, A[MAXN], D[MAXN], F[MAXN], W[MAXN], res1;
ll G[MAXN], res2;
void init_d()
{
re(i, n) E[i].pre = E[i].next = i; m = n;
}
void add_edge(int a, int b)
{
E[m].a = a; E[m].b = b; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
scanf("%d", &n);
A[0] = -INF; re1(i, n) {scanf("%d", &A[i]); A[i] -= i;} A[++n] = INF; n++;
}
void solve()
{
init_d(); F[0] = 0; G[0] = 0; D[0] = -INF; add_edge(0, 0); int len = 0, l, r, mid, x, maxw; ll sum, tmp;
re2(i, 1, n) {
if (A[i] >= D[len]) D[F[i] = ++len] = A[i]; else {
l = 0; r = len;
while (l < r) {
mid = l + r + 1 >> 1;
if (A[i] >= D[mid]) l = mid; else r = mid - 1;
}
D[F[i] = ++l] = A[i];
}
for (int p=E[F[i]-1].next; ; p=E[p].next) if (A[i] >= A[x = E[p].b]) break;
W[x] = 0; re2(j, x+1, i) if (A[j] < A[i]) W[j] = W[j - 1] + 1; else W[j] = W[j - 1] - 1;
sum = 0; maxw = -INF; G[i] = ~0Ull >> 2;
rre2(j, i, x) {
if (A[j] <= A[i] && F[j] == F[i] - 1) {
tmp = G[j] + sum; if (tmp < G[i]) G[i] = tmp;
tmp = G[j] + sum - (ll) (maxw - W[j]) * (A[i] - A[j]); if (tmp < G[i]) G[i] = tmp;
}
if (A[j] > A[i]) sum += A[j] - A[i]; else sum += A[i] - A[j];
if (W[j] > maxw) maxw = W[j];
}
add_edge(F[i], i);
}
res1 = n - F[n - 1] - 1; res2 = G[n - 1];
}
void pri()
{
cout << res1 << endl << res2 << endl;
}
int main()
{
init();
solve();
pri();
return 0;
}