gzhu 2013 Good Sequence 解题报告

A sequence contains n integers.

A sequence p₁, p₂, p₃...p_n is a good sequence if it satisfies p_{i ≤} p_i+1. i∈[1, n)<n)<n)<n)< p="">

KIDx likes good sequence very much. So he has made a random generator in order to generate lots of good sequences.

But unfortunately, there is something wrong with his generator so that it always generates bad sequences.

Now, KIDx has to transform every bad sequence to a good one. He can change any integer  in the sequence.

Your task is to find out the minimum number of integers KIDx has to change to get a good sequence.

Each case contains a positive integer n (n ≤ 5000) in the first line and a sequence which contains n integers p_i (0 ≤ p_i < 10⁸) in the second line.

For each test case, output the answer in a single line.

3
60 54 30
5
44 55 100 72 89

2
1


写下这题是为了纪念我蹩脚的DP！！！
求出最长非递减序列的个数，然后拿n - 个数 就是答案

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 const int maxn = 5000 + 10;
 6 int p[maxn], dp[2*maxn];
 7 
 8 int main()
 9 {
10     int i, j, n;
11     while (scanf("%d", &n) != EOF)
12     {
13         for (i = 1; i <= n; i++)
14          {
15             scanf("%d", &p[i]);
16             dp[i] = 1;
17          }
18         int ans = dp[1];
19         for (i = 2; i <= n; i++)
20         {
21             for (j = 1; j <= i-1; j++)
22             {
23                 if (p[j] <= p[i] && dp[j] + 1 >= dp[i])
24                 {
25                     dp[i] = dp[j] + 1;
26                     ans = max(ans, dp[i]);
27                 }
28             }
29         }
30         printf("%d\n", n-ans);
31     }
32     return 0;
33 }