題意：
給出一個(gè)序列（只包含1、2、3），問需要修改最少元素的個(gè)數(shù)使得這個(gè)序列遞增或遞減。
解法：
discuss里有說這題是LIS，沒有仔細(xì)想，我是自己推DP來做的。。
設(shè)sum1[i]為將數(shù)列前i個(gè)全部修正為1需要修改的次數(shù)，sum2、sum3亦同。
先寫修改最少元素使得序列遞增的做法
dp[j][i]=min(dp[j-1][i],sum[j][i]-sum[j][k]+dp[j-1][k],sum[j][i]);
觀察第二項(xiàng)
sum[j][i]-sum[j][k]+dp[j-1][k]，前一項(xiàng)是與k無關(guān)的常量，所以可以用一個(gè)堆來記錄前i-1項(xiàng)dp[j-1][k]-sum[j][k]的最小值，這樣可以省去一重枚舉k的復(fù)雜度
序列遞減做法亦同。
總復(fù)雜度O(nlog
n)
再次犯N個(gè)NC錯(cuò)誤：
1、最佳值應(yīng)該為dp[n],而不是dp[1..n]中的最小值。。。
2、開始寫DP方程的時(shí)候min里面漏了一項(xiàng)。。不過這個(gè)似乎不能怪我，題目理解有點(diǎn)歧義，我原來以為必須要用到1、2、3這3個(gè)元素。。所以dp方程里只有一項(xiàng)。。然后看discuss發(fā)現(xiàn)我理解錯(cuò)了，修正了下dp方程，結(jié)果。。汗。。
代碼：
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