题目描述
The cows are so very silly about their dinner partners. They have organized themselves into three groups (conveniently numbered 1, 2, and 3) that insist upon dining together. The trouble starts when they line up at the barn to enter the feeding area.
Each cow i carries with her a small card upon which is engraved)
indicating her dining group membership. The entire set of )
cows has lined up for dinner but it's easy for anyone to see that they are not grouped by their dinner-partner cards.
FJ's job is not so difficult. He just walks down the line of cows changing their dinner partner assignment by marking out the old number and writing in a new one. By doing so, he creates groups of cows like 111222333 or 333222111 where the cows' dining groups are sorted in either ascending or descending order by their dinner cards.
FJ is just as lazy as the next fellow. He's curious: what is the absolute mminimum number of cards he must change to create a proper grouping of dining partners? He must only change card numbers and must not rearrange the cows standing in line.
Each cow i carries with her a small card upon which is engraved
FJ's job is not so difficult. He just walks down the line of cows changing their dinner partner assignment by marking out the old number and writing in a new one. By doing so, he creates groups of cows like 111222333 or 333222111 where the cows' dining groups are sorted in either ascending or descending order by their dinner cards.
FJ is just as lazy as the next fellow. He's curious: what is the absolute mminimum number of cards he must change to create a proper grouping of dining partners? He must only change card numbers and must not rearrange the cows standing in line.
输入描述:
* Line 1: A single integer: N
* Lines 2..N+1: Line i describes the i-th cow's current dining group with a single integer:
输出描述:
* Line 1: A single integer representing the minimum number of changes that must be made so that the final sequence of cows is sorted in either ascending or descending order
示例1
输入
5
1
3
2
1
1
输出
1
说明
We would need at least two changes to turn this into an increasing sequence (changing both non-1's to a 1).
However, changing the first "1" to a "3" yields a decreasing sequence with just one change, which is optimal.
解答
【大意】给出N头奶牛的编号（1~3），每次修改一头奶牛编号代价是1，求最小的代价使得N头奶牛呈递增或递减。
【分析1】这道题奶牛编号的范围放的比较小。有一种方法可以直接求代价，而且没有编号限制。设S为代价，则可得Smin=（N-K），其中N是元素个数，K是这段数中最长的不下降（或不上升）序列的元素个数。
【分析1的证明】我们设在N个数中改变其中的S个数使其规范。假设把这S个数全部去掉，剩下的数必然呈不下降（或不上升）状态。我们想让S尽量的小，就是要使得（N-S）尽量的大。那么，当（N-S）最大的时候，S就是最小的。
【分析2】因为
,按照分析1的做法求最长不下降（不上升）序列，要用到
的方法，这样有点麻烦。根据数据小的特点，我们可以做一个DP。
设
是到第
个点，把其修改成
的最小代价。
如果
（即不用改了），%E2%80%A6%E2%80%A6)
否则我们就要用
的代价来修改，
【注意】因为题面中上升或下降都可以，所以要做两遍。
【分析1】这道题奶牛编号的范围放的比较小。有一种方法可以直接求代价，而且没有编号限制。设S为代价，则可得Smin=（N-K），其中N是元素个数，K是这段数中最长的不下降（或不上升）序列的元素个数。
【分析1的证明】我们设在N个数中改变其中的S个数使其规范。假设把这S个数全部去掉，剩下的数必然呈不下降（或不上升）状态。我们想让S尽量的小，就是要使得（N-S）尽量的大。那么，当（N-S）最大的时候，S就是最小的。
【分析2】因为
设
如果
否则我们就要用
【注意】因为题面中上升或下降都可以，所以要做两遍。
#include<stdio.h>
#include<algorithm>
#include<cstring>
const int INF=999999;
int f[30005][4],a[30005],ans,t,i,n;
using namespace std;
void get()
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=3;j++)
if (a[i]==j)
{
f[i][j]=INF;
for (int k=j;k>0;k--)
f[i][j]=min(f[i-1][k],f[i][j]);
}
else f[i][j]=f[i-1][j]+1;
}
}
int main()
{
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%ld",&a[i]);
get();
ans=min(f[n][1],f[n][2]);
ans=min(ans,f[n][3]);
memset(f,0,sizeof(f));
for (i=1;i<=n/2;i++) {t=a[i];a[i]=a[n-i+1];a[n-i+1]=t;}
get();
ans=min(f[n][1],ans);
ans=min(f[n][2],ans);
ans=min(f[n][3],ans);
printf("%ld",ans);
return 0;
} 来源：阿蒋
京公网安备 11010502036488号