心急的C小加 (求LDS) 证明

题目

题意: 给定n个元素，每个元素有x和y两种属性。元素A < 元素B的定义为: A.x <= B.x且A.y <= B.y。我们需要找到最少数量的非严格单调递增子序列。其实这个问题等价于求最长下降子序列，后续会有证明。

解法:(抄实验报告了属于是)

此题和arc某场的B题相似，都是先排序，再求LIS，只不过此题是求LDS.
用到了Dilworth定理：偏序集的最少反链划分数等于最长链的长度.
也就是说把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。对于本题恰好反过来，要求划分最少的最长不降子序列，等于这个数列的最长下降子序列的长度。
证明:
【定理】
在X中，对于元素a，如果任意元素b，都有a≤b，则称a为极小元。

定理1：令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
虽然这两个定理内容相似，但第一个定理证明要简单一些。此处就只证明定理1。
证明：设p为最少反链个数
(1)先证明X不能划分成小于r个反链。由于r是最大链C的大小，C中任两个元素都可比，因此C中任两个元素都不能属于同一反
链。所以p>=r。
(2)设X1＝X，A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A2是X2中极小元的集合，从X2中删除A2得到X3……，最终会有一个Xk非空而Xk+1为空。于是A1,A2,…,Ak就是X的反链的划分，同时存在链a1<=a2<=…<=ak，其中ai在Ai内。由于r是最长链大小，因此r>=k。由于X被划分成了k个反链，因此r>=k>=p。
(3)因此r=p，定理1得证。
结论: 最少链划分 = 最长反链长度
简单来说就是该题答案为最长下降子序列的长度。
解法:
优先按照任意一维属性排序，这一维排好序就不用管了。
只看另一维度，求最少数量的非严格单调递增子序列。等价于求最长下降子序列。套用LIS贪心nlogn的模板即可.
证明:
首先考虑贪心.
贪心流程:
对于当前数x:
1.如果目前已有的子序列的结尾都 > x,新建一个子序列.
2.选择一个最大的满足结尾元素<=x的子序列，接上x.
证明贪心算法的正确性:
Exchange Argument法.(简单来说是证明A >= B 且 A <= B)
将Greedy Algorithm得到的解记为A，假设A不是最优的，那么存在最优解O.(O是arbitrary的)
必定有A != O.说明存在元素A和O选择不同。假设对于第i个元素的选择，存在子序列结尾满足<=x.A选择了子序列中结尾最大的seq1，O选择了其他子序列seq2.必定有seq1[last] >= seq2[last],因为x >= seq1[last],所以x >= seq2[last].我们构造O’,O’为O将x从seq2结尾交换到seq1. |O’| = |O|.说明O’不必O差，即O’<= O.
由于一共有n个元素，A和O最多有n个元素选择不同。最多通过n(Polynomial)次交换，可以消除所有A和O的不同，同时保证算法的质量不比O差。
所以A是as good as O的。因为O是arbitrary的最优解,所以A是最优的.(optimal)

代码:

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
//#include  
#include  
#include  
#include  
#include  
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)  
#define fir(i,a,b) for(int i=a;i<=b;++i)   
#define mem(a,x) memset(a,x,sizeof(a))  
#define p_ priority_queue  
// round() 四舍五入 ceil() 向上取整 floor() 向下取整  
// lower_bound(a.begin(),a.end(),tmp,greater()) 第一个小于等于的  
// #define int long long //QAQ  
using namespace std;  
typedef complex CP;  
typedef pair PII;  
typedef long long ll;  
// typedef __int128 it;  
const double pi = acos(-1.0);  
const int INF = 0x3f3f3f3f;  
const ll inf = 1e18;  
const int N = 2e5+10;  
const int M = 1e6+10;  
const int mod = 1e9+7;  
const double eps = 1e-6;  
inline int lowbit(int x){ return x&(-x);}  
templatevoid write(T x)  
{  
    if(x<0)  
    {  
        putchar('-');  
        x=-x;  
    }  
    if(x>9)  
    {  
        write(x/10);  
    }  
    putchar(x%10+'0');  
}  
template void read(T &x)  
{  
    x = 0;char ch = getchar();ll f = 1;  
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}  
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;  
}  
int n,m,k,T;  
struct node{  
    int x,y;  
    bool operator < (const node&rhs)  
    {  
        return (x <= rhs.x && y <= rhs.y);  
    }  
    bool operator == (const node&rhs)  
    {  
        return (x == rhs.x && y == rhs.y);   
    }  
    bool operator > (const node&rhs)  
    {  
        return (x >= rhs.x && y >= rhs.y);  
    }  
}a[5002];  
bool cmp(const node&a,const node&b)  
{  
     if(a.x != b.x) return a.x < b.x;  
     return a.y < b.y;  
}  
int va[5002];  
int f[5002]; //表示长度为i的单调下降子序列的结尾  
int cnt;  
void solve()  
{  
    read(n);  
    for(int i=1;i<=n;++i)  
    {  
        read(a[i].x),read(a[i].y);  
    }  
    sort(a+1,a+n+1,cmp);  
    // for(int i=1;i<=n;++i)  
    // {  
//        
    // }  
    for(int i=1;i<=n;++i)  
    {  
        va[i] = a[i].y;  
    }  
    // for(int i=1;i<=n;++i)  
    // {  
       // cout<()) - f;  
            f[idx] = va[i];  
        }  
    }  
    int ans = cnt;  
    write(ans); puts("");  
}  
signed main(void)  
{    
   // T = 1;  
   // OldTomato; cin>>T;  
   read(T);  
   while(T--)  
   {  
     solve();  
   }  
   return 0;  
}

心急的C小加 (求LDS) 证明

C/C++/C#相关栏目本月热门文章