首页 > 代码库 > 51nod 1294：修改数组
51nod 1294：修改数组
51nod 1294：修改数组
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1294
题目大意：将一个序列修改成严格递增序列，最少需要替换几个数.
dp
这道题相当巧妙.
最小的满足条件的序列为$\{1,2,3,...,n\}$，若$a_i < i$那么该数必须被修改.
然后对序列$\{a_1-1,a_2-2,a_3-3,...,a_n-n\}$找出最长不递减子序列，除去该子序列外的数均要被修改.
复杂度$O(nlgn)$.
代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 #define N 100005 4 using namespace std; 5 int n,x,ans,dp[N],k; 6 int main(void){ 7 scanf("%d",&n); 8 for(int i=1;i<=n;++i){ 9 scanf("%d",&x);x-=i;10 if(x<0)continue;11 int idx=upper_bound(dp,dp+k,x)-dp;12 dp[idx]=x;13 if(idx==k)k++;14 }15 printf("%d\n",n-k);16 }
51nod 1294：修改数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。