讨论/技术交流/终结!求助:大家帮忙看看这个题咋做/
终结!求助:大家帮忙看看这个题咋做

现在有一个长度为n的数组,特殊之处在于数组的每一位都不是一个确定的数字,而是一个区间,你可以从区间内任选一个整数作为该位置的值。

现在想给每个位置都确定一个值,使得最终的结果序列的最长上升子序列尽量的长,请问这个长度最长能有多长。

输入数据
第一行一个正整数n,n<=1000

接下来n行每行两个正整数:l和r,它们代表该位置对应的闭区间[l,r],其中1<=l<=r<=1000

样例输入
5
1 2
2 3
3 5
1 3
4 7

样例输出
4
1
共 3 个回复

考虑以普通「最长上升子序列」的优化方式用到的状态进行动态规划。

f[i]f[i] 表示长度为 ii 的最长上升子序列的最后一个元素的最小值,如果当前遍历到的元素为区间 [lk,rk][l_k, r_k],那么可以对所有满足 f[i]<rkf[i] < r_kf[i+1]f[i+1] 更新为 max(f[i]+1,lk)\max ( f[i]+1, l_k )。总时间复杂度为 O(n2)O(n^2)

2

浏览其他AC代码发现另一种解法,现把代码贴出来供大家思考

#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main()
{
 int m;
 int left,right;
 cin>>m;
 for(int i=1;i<=m;i++)
 {
     cin>>left>>right;
     for(int j=1;j<=1000;j++)
     {
         dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
         if(j>=left&&j<=right)
            dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
     }
 }
 cout<<dp[m][1000];
}

大佬我稍微改了下,f[i+1]=min(f[i+1],max(f[i]+1,lk))\displaystyle f[i+1]=min(f[i+1],max(f[i]+1,l_k))
AC代码贴在这里

int main(){
    int n;
    cin>>n;
    vector<vector<int>> seq(n,vector<int>(2));
    for(int i=0;i<n;i++)
        cin>>seq[i][0]>>seq[i][1];
    vector<int> dp;
    dp.emplace_back(0);
    for(int i=0;i<n;i++){
        int m=dp.size();
        for(int j=m-1;j>=0;j--){
            if(dp[j]<seq[i][1]){
                int t=max(dp[j]+1,seq[i][0]);
                if(j==m-1)
                    dp.emplace_back(t);
                else
                    dp[j+1]=min(dp[j+1],t);
            }
        }
    }
    cout<<dp.size()-1;
}