sqlite 做网站数据库,软件外包专业就业方向,内容营销ppt,网页编辑软件朱题意
给出一个序列#xff0c;允许删除一个元素#xff0c;并将任意元素的值修改为任意整数#xff0c;问最少修改多少个元素使得序列变成严格单调递增的序列#xff1f; 题解
这道题目很具有启发性#xff1a; 不考虑删除元素#xff0c;原数列各个数值减去他们下标得…题意
给出一个序列允许删除一个元素并将任意元素的值修改为任意整数问最少修改多少个元素使得序列变成严格单调递增的序列 题解
这道题目很具有启发性 不考虑删除元素原数列各个数值减去他们下标得到一个新的序列那么新的序列的最长不减序列就是不需要修改的元素个数len需要修改的元素个数就是n-len即可。
这道题也是这么做的我们枚举要删除的元素下标为kkk，并且得到以元素k#x2212;1" role="presentation" style="position: relative;">k−1k−1k-1为结尾的最长不减序列的长度len1len1len_1以及得到以元素iii为开始的最长不减序列的长度len2" role="presentation" style="position: relative;">len2len2len_2要求a[i]1a[k−1]a[i]1a[k−1]a[i]+1 >= a[k-1]因为这样才能将两部分拼接起来那么这就是删除元素kkk时候得到的最多不需修改的元素的数量，枚举k" role="presentation" style="position: relative;">kkk取最大值即可。
怎样维护以a[i]a[i]a[i]结尾的最长不减序列的长度和以a[i]a[i]a[i]开头的最长不减序列的长度呢
思路就是dp 可持久化/动态开点线段树。dp[a[i]]dp[a[i]]dp[a[i]]表示以a[i]结尾的不减序列的最长长度那么dp[a[i]]max(dp[1],dp[2],...,dp[a[i]])1dp[a[i]]max(dp[1],dp[2],...,dp[a[i]])1dp[a[i]] = max(dp[1],dp[2],...,dp[a[i]])+1线段树的动态开点功能使得不需要离散化。 代码
#include iostream
#include cstring
#include cstdio
#include algorithm
#include cstring
using namespace std;
const int MAXN 400008;
struct segtree{int root[MAXN];int val[MAXN * 20];int lson[MAXN * 20];int rson[MAXN * 20];int index;int n;void init(int N){n N;index 0;memset(val,0,sizeof(root));memset(val,0,sizeof(val));memset(lson,0,sizeof(lson));memset(rson,0,sizeof(rson));}void insert(int num,int rt,int l,int r,int v){int nrt index;lson[nrt] lson[rt];rson[nrt] rson[rt];val[nrt] val[rt];rt nrt;if(l r) {val[rt] v;return ;}int mid (l r) / 2;if(num mid) insert(num,lson[rt],l,mid,v);else insert(num,rson[rt],mid1,r,v);val[rt] max(val[lson[rt]],val[rson[rt]]);}int _query(int rt,int l,int r,int ul,int ur){if(r ul || l ur) return 0;if(ul l r ur) return val[rt];int mid (l r) / 2;int a _query(lson[rt],l,mid,ul,ur);int b _query(rson[rt],mid1,r,ul,ur);return max(a,b);}void putone(int i,int pos,int num){root[i] root[i-1];insert(pos,root[i],1,n,num);}
}seg,segp;
const int inf 1e9MAXN;
int n;
int a[MAXN],dp[MAXN];
int main(){seg.init(inf);segp.init(inf);cinn;for(int i 1;i n;i){scanf(%d,a[i]);a[i] a[i]-iMAXN;}int ans 0;for(int i n;i 1;--i){int mxlen seg._query(seg.root[n-i],1,inf,a[i],inf);seg.putone(n-i1,a[i],mxlen1);ans max(ans,mxlen1);//couti:mxlenendl;}for(int i 1;i n;i){int mxlen segp._query(segp.root[i-1],1,inf,1,a[i]);segp.putone(i,a[i],mxlen1);ans max(ans,mxlen1);//couti:mxlenendl;}for(int i 2;i n;i){int len1 segp._query(segp.root[i],1,inf,a[i-1],a[i-1]);int len2 seg._query(seg.root[n-i],1,inf,a[i-1]-1,inf);ans max(ans,len1len2);}coutmax(0,n-ans-1)endl;return 0;
}
