序列變換

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1200????Accepted Submission(s): 448

Problem Description 我們有一個數列A1,A2...An，你現在要求修改數量最少的元素，使得這個數列嚴格遞增。其中無論是修改前還是修改后，每個元素都必須是整數。 請輸出最少需要修改多少個元素。

?

Input 第一行輸入一個T(1≤T≤10)，表示有多少組數據
每一組數據：
第一行輸入一個N(1≤N≤105)，表示數列的長度
第二行輸入N個數A1,A2,...,An。
每一個數列中的元素都是正整數而且不超過106。

?

Output 對于每組數據，先輸出一行
Case #i:
然后輸出最少需要修改多少個元素。

?

Sample Input 2 2 1 10 3 2 5 4

?

Sample Output Case #1: 0 Case #2: 1

?

Source 2015年百度之星程序設計大賽 - 初賽(2)

題解：

改變系列使成為單調遞增子序列；那么只需要dp[i]-dp[j]>=i-j就好了；再加上單調遞增子序列的求法；

dp[i]-dp[j]>=i-j即為dp[i]-i>=dp[j]-j;

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; const int MAXN = 1e5 + 100; int num[MAXN]; int dp[MAXN]; vector<int>vec; /* int main(){int T, N, kase = 0;scanf("%d", &T);while(T--){vec.clear();scanf("%d", &N);for(int i = 0; i < N; i++){scanf("%d", num + i);num[i] -= i;if(upper_bound(vec.begin(), vec.end(), num[i]) == vec.end()){vec.push_back(num[i]);}else{int p = upper_bound(vec.begin(), vec.end(), num[i]) - vec.begin();vec[p] = num[i];}}printf("Case #%d:\n%d\n", ++kase, N - vec.size());}return 0; } */int main(){int T, N, kase = 0;scanf("%d", &T);while(T--){scanf("%d", &N);memset(dp, 0, sizeof(dp));int ans = 0;for(int i = 0; i < N; i++){scanf("%d", num + i);for(int j = 0; j < i; j++){if(num[i] - num[j] >= i - j){dp[i] = dp[j] + 1;ans = max(ans, dp[i]);}}}printf("Case #%d:\n%d\n", ++kase, N - ans - 1);}return 0; }

?

總結

以上是生活随笔為你收集整理的序列变换（Lis变形）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。