P2896 [USACO08FEB] Eating Together S
题目描述
FJ 的奶牛们在吃晚饭时很傻。他们把自己组织成三组（为了方便，将它们编号为 \(1,2,3\)），坚持一起用餐。当他们在谷仓排队进入喂食区时，麻烦就开始了。
每头奶牛都随身带着一张小卡片，小卡片上刻的是 \(D_i\)（\(1\le D_i\le 3\)）表示她属于哪一组。所有的 \(N\)（\(1\le N\le 30000\)）头奶牛排队吃饭，但他们并不能按卡片上的分组站好。
FJ 的工作并不是那么难。他只是沿着牛的路线走下去，把旧的号码标出来，换上一个新的。通过这样做，他使奶牛的就餐组按他们的晚餐卡片按升序或降序排列，比如 111222333 或 333222111。
FJ 和其他人一样懒惰。他很好奇：怎样他才能进行适当的分组，使得他只要修改最少次数的数字？由于奶牛们已经很长时间没有吃到饭了，所以“哞哞”的声音到处都是，FJ 只能更换卡号，而不能重新排列已经排好队的奶牛。
输入格式
- 第 \(1\) 行：一个整数：\(n\)
- 第 \(2\sim n+1\) 行：第 \(i+1\) 行描述第 \(i\) 个奶牛目前的分组
输出格式
一个整数，表示必须做出的最小变化数，使得奶牛的就餐组按他们的晚餐卡片按升序或降序排列。
输入输出样例 #1
输入 #1
5
1
3
2
1
1输出 #1
1说明/提示
解题思路：第一种比较容易想到的，就是记录每个位置选1，2，3，是的最优解。设dp[i][j]表示修改前i位使得其合法且最后一位为j的最小代价.
#include<bits/stdc++.h>//导入工具
using namespace std;
int a[32333];
int dp[3][32333];
int main(){//程序入口 nullint n;cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];}dp[0][0]=0;dp[1][0]=0;dp[2][0]=0;for(int i=1;i<=n;i++) {if(a[i]==1) {dp[0][i]=dp[0][i-1];dp[1][i]=min(dp[1][i-1]+1,dp[0][i-1]+1);dp[2][i]=min(dp[0][i-1]+1,min(dp[1][i-1]+1,dp[2][i-1]+1));}if(a[i]==2) {dp[0][i]=dp[0][i-1]+1;dp[1][i]=min(dp[1][i-1],dp[0][i-1]);dp[2][i]=min(dp[0][i-1]+1,min(dp[1][i-1]+1,dp[2][i-1]+1));}if(a[i]==3) {dp[0][i]=dp[0][i-1]+1;dp[1][i]=min(dp[1][i-1]+1,dp[0][i-1]+1);dp[2][i]=min(dp[0][i-1],min(dp[1][i-1],dp[2][i-1]));}}//3 1 3 2 1// for(int i=0;i<3;i++) {// for(int j=1;j<=n;j++) {// cout<<dp[i][j]<<" ";// }// cout<<endl;// }int q=min(dp[0][n],min(dp[1][n],dp[2][n]));dp[0][0]=0;dp[1][0]=0;dp[2][0]=0;for(int i=1;i<=n;i++) {if(a[i]==1) {dp[0][i]=min(dp[0][i-1],min(dp[1][i-1],dp[2][i-1]));dp[1][i]=min(dp[1][i-1]+1,dp[2][i-1]+1);dp[2][i]=dp[2][i-1]+1;}if(a[i]==2) {dp[0][i]=min(dp[0][i-1]+1,min(dp[1][i-1]+1,dp[2][i-1]+1));dp[1][i]=min(dp[1][i-1],dp[2][i-1]);dp[2][i]=dp[2][i-1]+1;}if(a[i]==3) {dp[0][i]=min(dp[0][i-1]+1,min(dp[1][i-1]+1,dp[2][i-1]+1));dp[1][i]=min(dp[1][i-1]+1,dp[2][i-1]+1);dp[2][i]=dp[2][i-1];}}// for(int i=0;i<3;i++) {// for(int j=1;j<=n;j++) {// cout<<dp[i][j]<<" ";// }// cout<<endl;// }int w=min(dp[0][n],min(dp[1][n],dp[2][n]));cout<<min(q,w)<<endl;return 0;//程序出口
}第二种写法；题目要求最后序列是单调不下降或者单调不上升。这里需要我们想到最长上升子序列（LIS）。修改数字分为两种情况，情况一修改的是最长上升子序列的组成部分，情况二不是最长上升子序列。不难想到，情况二无论修改哪个数字都有方法使LIS程度增加1，并且此题最多一次操作能使LIS程度增加1，所以修改非LIS上数能得到更优。如果修改LIS上一个数字能使LIS更优，则必定存在一个和这个LIS等长的LIS，将那个视为LIS即回到情况二。
这样此题便成为求n−max(LIS,LDS)
#include<bits/stdc++.h>
using namespace std;
int arr[32333];
int dp[32333];int main()
{int n;cin>>n;for(int i=1;i<=n;i++) {cin>>arr[i];}int ans=0;for(int i=1;i<=n;i++) {dp[i]=1;for(int j=i-1;j>=1;j--) {if(arr[i]>=arr[j]) {dp[i]=max(dp[i],dp[j]+1);}if (arr[i]==arr[j]) {//优化break;}}ans=max(ans,dp[i]);}memset(dp,0,sizeof(dp));for(int i=n;i>=1;i--) {dp[i]=1;for(int j=i+1;j<=n;j++) {if (arr[i]>=arr[j]) {dp[i]=max(dp[i],dp[j]+1);}if (arr[i]==arr[j]) {break;}}ans=max(ans,dp[i]);}cout<<n-ans<<endl;return 0;
}