题意：
给出一个序列（只包含1、2、3），问需要修改最少元素的个数使得这个序列递增或递减。
解法：
discuss里有说这题是LIS，没有仔细想，我是自己推DP来做的。。
设sum1[i]为将数列前i个全部修正为1需要修改的次数，sum2、sum3亦同。
先写修改最少元素使得序列递增的做法
dp[j][i]=min(dp[j-1][i],sum[j][i]-sum[j][k]+dp[j-1][k],sum[j][i]);
观察第二项
sum[j][i]-sum[j][k]+dp[j-1][k]，前一项是与k无关的常量，所以可以用一个堆来记录前i-1项dp[j-1][k]-sum[j][k]的最小值，这样可以省去一重枚举k的复杂度
序列递减做法亦同。
总复杂度O(nlog
n)
再次犯N个NC错误：
1、最佳值应该为dp[n],而不是dp[1..n]中的最小值。。。
2、开始写DP方程的时候min里面漏了一项。。不过这个似乎不能怪我，题目理解有点歧义，我原来以为必须要用到1、2、3这3个元素。。所以dp方程里只有一项。。然后看discuss发现我理解错了，修正了下dp方程，结果。。汗。。
代码：
1
# include <iostream>
2using namespace std;
3# include <queue>
4# include <vector>
5# include <cstring>
6# include <cstdlib>
7# define min(a,b) ((a)<(b)?(a):(b))
8const int N=30005;
9int s[3][N],*sum,n,dp[N],tdp[N];
10struct cmp
11
{
12
bool operator()(const int &a,const int &b) const
13
{
14 return dp[a]-(a-sum[a])>dp[b]-(b-sum[b]);
15
}
16
};
17priority_queue<int,vector<int>,cmp> q;
18void print()
19{
20 for(int i=1;i<=n;i++)
21 cout<<dp[i]<<" ";
22 cout<<endl;
23 // system("pause");
24}
25int main()
26{
27 memset(s,0,sizeof(s));
28 cin>>n;
29 for(int i=1;i<=n;i++)
30 {
31 for(int j=0;j<3;j++)
32 s[j][i]=s[j][i-1];
33 int t;
34 cin>>t;
35 s[t-1][i]++;
36 }
37 int ans=0xfffffff;
38 for(int i=1;i<=n;i++)
39 dp[i]=i-s[0][i];
40 // print();
41 for(int i=2;i<=3;i++)
42 {
43 while(!q.empty()) q.pop();
44 // memset(tdp,0,sizeof(tdp));
45 sum=s[i-1];
46 q.push(1);
47 tdp[1]=min(dp[1],1-sum[1]);
48 for(int j=2;j<=n;j++)
49 {
50 tdp[j]=min(dp[q.top()]-(q.top()-sum[q.top()])+j-sum[j],dp[j]);
51 q.push(j);
52 }
53 for(int j=1;j<=n;j++)
54 tdp[j]=min(tdp[j],j-sum[j]);
55 memcpy(dp,tdp,sizeof(dp));
56 // print();
57 }
58
59 ans=min(ans,dp[n]);
60 for(int i=1;i<=n;i++)
61 dp[i]=i-s[2][i];
62 // print();
63 for(int i=2;i<=3;i++)
64 {
65 while(!q.empty()) q.pop();
66 // memset(tdp,0,sizeof(tdp));
67 sum=s[3-i];
68 q.push(1);
69 tdp[1]=min(dp[1],1-sum[1]);
70 for(int j=2;j<=n;j++)
71 {
72 tdp[j]=min(dp[j],dp[q.top()]-(q.top()-sum[q.top()])+j-sum[j]);
73 q.push(j);
74 }
75 for(int j=1;j<=n;j++)
76 tdp[j]=min(tdp[j],j-sum[j]);
77 memcpy(dp,tdp,sizeof(dp));
78 // print();
79 }
80 ans=min(ans,dp[n]);
81 cout<<ans<<endl;
82 // system("pause");
83 return 0;
84}
85