最近做了两道LIS模型题,感觉到模型比较好,总结一下囧。
【1】[HAOI2007]上升序列
预处理:设F[i]为以i开头的最长上升序列的长度,怎么求不用说了吧囧……
假设目前需要求长度为M的、标号字典序最小的上升序列,显然其第一个元素A[i]必须满足F[i]>=M(注意,不是等于,是大于等于!),找到满足这个条件的最小的i即可。然后,设目前已经求出了该序列的第x个元素为A[y],则第(x+1)个元素A[z]需要满足的条件是A[z]>A[y],且F[z]=F[y]-1,找到满足这个条件的最小的z即为该序列的第(x+1)个元素。按照这种方法,扫描一遍就可以求出整个序列,时间复杂度为O(N)。如果整个序列的最长上升序列长度<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 == 1return; 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) returnelse 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]数字序列
首先,由于序列的所有元素都是整数,所以可以将原序列的所有元素减去它的下标,这样就把上升序列转化为不下降序列了。
第一问的结果显然就是(N-新序列的最长不下降序列长度)。关键在于第二问。以下A均表示新序列。
设F[i]为以A[i]结尾的最长不下降序列长度(同样,求法不用说了),G[i]为在A[i]不修改的前提下将A[0..i]转变为不下降序列的最小修改量。首先求出F[i],然后在求G[i]时,枚举上一个“不动点”(就是不修改的元素)A[j](显然必须满足A[j]<=A[i]且F[j]=F[i]-1),这样最小修改量就是G[j]+(将A[j..i]转变为不下降序列的最小修改量)。可以证明,A[j..i]的最优修改方案必然是将A[j+1..t]全部修改为A[j],A[t+1..i]全部修改为A[i],这里t是一个[j..i]范围的值。问题就是如何求出最优的t?
一开始,假设t=j,即把A[j+1..i-1]全部修改为A[i],计算出修改量,设为S。然后,由于A[j+1..i-1]之间的元素要么小于A[j],要么大于A[i](这个是显然的囧),我们把小于A[j]的元素称为“小数”,把大于A[i]的元素称为“大数”,则当t取t0时,修改量为S-(A[i]-A[j])*(A[j+1..t0]中的“小数”个数减去“大数”个数)。这样,只需扫描一下,求出使得(A[j+1..t0]中的“小数”个数减去“大数”个数)值最大的t0即可。
当然还有一个问题,对于同一个i,满足“A[j]<=A[i]且F[j]=F[i]-1”的元素个数可能有很多,如果一个一个枚举,一个一个扫描,会很慢的囧……解决方法是,求出满足这个条件的j中最小的一个,设为j0,然后把A[j0+1..i-1]中的所有“小数”和“大数”全部处理出来,然后用类似前缀和的方法就能搞了囧……当然,为了找到j0,需要建一个二分图,边为(F[i], i)。
最后,为了方便,可以把A序列的左边加一个-INF,右边加一个+INF。最后总的时间复杂度,理论上为O(N2),但由于是随机数据,所以远远达不到这个级别。

代码:
#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(00); 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+ 1else 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;
}


Feedback

# re: 【AHOI2013复仇】两道LIS模型题总结  回复  更多评论   

2013-07-08 21:34 by nike0good
我觉得可以用线段树套Splay O(log^2n)求区间中位数

# re: 【AHOI2013复仇】两道LIS模型题总结  回复  更多评论   

2015-03-09 17:14 by dreamATD
[HAOI2006]数字序列里那个二分图是干什么的?

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理