hdu 1257

╰+攻爆jí腚メ 2023-03-01 12:58 10阅读 0赞

![博客图片][format_png]

## 问题描述 ##

给出一个序列,计算这个序列的递增子序列的最大长度.

## 解法 ##

用一个数组`dp`记录到每个数的最长的递增子列,用一个数组记录数列,`dp[j]`表示已第`j`个元素结尾的最长的递增子列的长度,`max_len`表示比第`i`个元素小的最长的递增子列的长度,当以当前元素为结尾的最长递增子列比那个`max_len`大并且当前元素比`i`小时,更新`max_len`,最后`dp[i]`的值就是这个`max_len+1`,没经过内层一轮循环更新全局的最优解,于是得到下面的程序:

void LCS(int n){
        
            memset(dp, 0, sizeof(dp));
            memset(heights, 0, sizeof(heights));
            for (int i = 1; i <= n; i++) {
        
                scanf("%lld", &heights[i]);
            }
            dp[1] = 1;
            ll ans = 0ll;
            for (int i = 2; i <= n; i++) {
        
                int max_len = 0;
                // for(int j = 1; j <= n; j++) {
        
                //     printf("%lld ", dp[j]);
                // }
                // printf("\n");
                for (int j = 1; j <= i; j++) {
        
                    if( dp[j] > max_len && heights[j] < heights[i]){
        
                        max_len = dp[j];
                    }
                }
                dp[i] = max_len + 1;
                if (ans < dp[i])
                    ans = dp[i];
            }
            // for(int j = 1; j <= n; j++) {
        
            //     printf("%lld ", dp[j]);
            // }
            // printf("\n");
            printf("%lld\n", ans);
        }

除了这种利用DP来解决的方法,还有一种基于序列本身的特征的方法,借助于一个数组`d`计算当前`LIS`的长度.初始时设置`d[0]=heights[1]`,然后开始迭代处理`heights`中的每一个数:

1.  如果`heights[i]>d[cnt-1]`,那么`d[cnt++]=heights[i]`,也就是说如果当前的高度比`d`中最后一个还高,那么这个应该为`LIS`贡献一个长度;
2.  如果`heights[i]>d[cnt-1]`不成立,那么从`d`中找到第一个比这个`heights[i]`大的位置,然后将这个位置的数替换为`heights[i]`.有两个原因,第一个这个不会影响中的`LIS`的长度;其次,`heights`后面未处理的数,可能比前面的数都小,但是会构成最优的`LIS`,这样替换掉`d`中第一个比`heights[i]`给更小的数字留下机会,`heights[i]`可能在`LIS`中,被替换的数字更有可能不在`LIS`中.

ll d[N];
    
       void lis(int n){
        
           memset(d, 0, sizeof(d));
           memset(heights, 0, sizeof(heights));
           for(int i=1; i<= n; i++){
        
               scanf("%lld", &heights[i]);
           }
           d[0] = heights[1];
           int len = 1;
           for (int i = 2; i <= n; i++){
        
               if( heights[i] > d[len-1])
                   d[len++] = heights[i];
               else{
        
                   int t = lower_bound(d, d + len, heights[i])-d;
                   d[t] = heights[i];
               }
           }
           printf("%d\n", len);
       }

## 题目链接 ##

[hdu1257][]

## 题目概述 ##

有一种反导系统,第一发导弹可以拦截任意高度的导弹,但是后面的每一发都不能超过前面一发发射的高度,现在给出一些地方发射的导弹高度的序列,计算需要的最少的拦截系统的数量.

## 想法 ##

可以直接用贪心来模拟计算,对于地方发来的导弹,首先从已经部署的翻到系统中找一找有没有可拦截高度比这个大的,如果有那么找可拦截的最小的,更高的留给后面高度更高的导弹,如果没有,那么需要额外部署一套反导系统.没进行一次拦截,要更新翻到系统可以拦截的最高高度.可以得到下面这个程序

void solve(int n){
        
           int cnt = 0;
           fill(ans, ans + N, INT_MAX);
           for(int i = 0; i < n; ++i){
        
               int t;
               scanf("%d", &t);
               int choice = cnt;
               for (int j = 0; j <= cnt; ++j){
        
                   // printf("choice=%d,ans[choice]=%lld,cnt=%d,t=%d,j=%d,ans[j]=%lld\n", choice,ans[choice], cnt, t, j, ans[j]);
                   if( ans[j] >= t && ans[j] <= ans[choice]){
        
                       choice = j;
                   }
               }
               // printf("%d ", choice);
               ans[choice] = t;
               if(choice == cnt){
        
                   ++cnt;
               }
           }
           printf("%d\n", cnt);
       }

如果把每个翻到系统拦截的导弹高度单独拎出来看的话,会发现每个拦截系统拦截的导弹高度序列恰好是一个单调递减的序列.假设现在有两个反导系统拦截得到的序列X,Y,对于`Y`中至少有一个高度大于`X`中的某个高度,从每一个拦截系统中拿出一个数,可以构成一个单调递增的序列,拦截系统的数量就是这个序列的长度.

## 代码 ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 300005;
    
    ll ans[N];
    
    
    void solve(int n){
        
        int cnt = 0;
        fill(ans, ans + N, INT_MAX);
        for(int i = 0; i < n; ++i){
        
            int t;
            scanf("%d", &t);
            int choice = cnt;
            for (int j = 0; j <= cnt; ++j){
        
                // printf("choice=%d,ans[choice]=%lld,cnt=%d,t=%d,j=%d,ans[j]=%lld\n", choice,ans[choice], cnt, t, j, ans[j]);
                if( ans[j] >= t && ans[j] <= ans[choice]){
        
                    choice = j;
                }
            }
            // printf("%d ", choice);
            ans[choice] = t;
            if(choice == cnt){
        
                ++cnt;
            }
        }
        printf("%d\n", cnt);
    }
    
    ll dp[N];
    ll heights[N];
    
    void LCS(int n){
        
        memset(dp, 0, sizeof(dp));
        memset(heights, 0, sizeof(heights));
        for (int i = 1; i <= n; i++) {
        
            scanf("%lld", &heights[i]);
        }
        dp[1] = 1;
        ll ans = 0ll;
        for (int i = 2; i <= n; i++) {
        
            int max_len = 0;
            // for(int j = 1; j <= n; j++) {
        
            //     printf("%lld ", dp[j]);
            // }
            // printf("\n");
            for (int j = 1; j <= i; j++) {
        
                if( dp[j] > max_len && heights[j] < heights[i]){
        
                    max_len = dp[j];
                }
            }
            dp[i] = max_len + 1;
            if (ans < dp[i])
                ans = dp[i];
        }
        // for(int j = 1; j <= n; j++) {
        
        //     printf("%lld ", dp[j]);
        // }
        // printf("\n");
        printf("%lld\n", ans);
    }
    
    ll d[N];
    
    void lis(int n){
        
        memset(d, 0, sizeof(d));
        memset(heights, 0, sizeof(heights));
        for(int i=1; i<= n; i++){
        
            scanf("%lld", &heights[i]);
        }
        d[0] = heights[1];
        int len = 1;
        for (int i = 2; i <= n; i++){
        
            if( heights[i] > d[len-1])
                d[len++] = heights[i];
            else{
        
                int t = lower_bound(d, d + len, heights[i])-d;
                d[t] = heights[i];
            }
        }
        printf("%d\n", len);
    }
    
    int main(int argc, const char** argv) {
        
        int n;
        while(~scanf("%d", &n)){
        
            // solve(n);
            // LCS(n);
            lis(n);
        }
        return 0;
    }

## 其它 ##

[format_png]: /images/20230208/e1fb7f5f54a14558945ade9faf997146.png
[hdu1257]: http://acm.hdu.edu.cn/showproblem.php?pid=1257