P2837 晚餐队列安排

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

此题可能用动规不太好做，主要是状态转移方程很难想个人认为，思维发散的大佬们忽视。

我看了这位大佬的 dp 题解后才想到了方程，在此受我一膜%%%

嗯，说下思路：

先用 a [ i ] 数组存一下输入的编号；

然后用二维数组 dp [ i ][ 0/1 ] 来表示当前第 i 头奶牛的编号改成 1 或 2 所用的最少次数（0 表示改成 1，1 表示改成 2）

当然要考虑当前第 i 的奶牛的编号是 1 还是 2；

重点来了！！！

如果是 1 ，那么 dp [ i ][ 0 ] = dp [ i-1 ][ 0 ]；dp [ i ][ 1 ] = min ( dp [ i-1 ][ 0 ]，dp [ i-1 ][ 1 ] ) + 1；

说一下啥意思：当前第 i 头奶牛的编号为 1，那么将这头奶牛的编号改为 1（其实不用改）的最小次数就是第 i - 1 头奶牛的编号改成 1 的最小次数，因为你必须保证前面的编号都为 1；

如果将这头奶牛的编号改成 2（这时候就要改了，所以后面要 +1）的最小次数就是第 i-1 头奶牛的编号改成 1 或 2 的最小次数，因为编号是 2 不能保证前面的编号是 1 还是 2，所以要求最小值；

同理，如果是 2 那么 dp [ i ][ 0 ] = dp [ i-1 ][ 0 ] + 1；dp [ i ][ 1 ] = min ( dp [ i-1 ][ 0 ]，dp [ i-1 ][ 1 ] )；

此时 +1 就挪到了第一个状态转移方程里，因为 2 改成 1 次数要 +1 是吧。

终于搞完了状态转移方程，这个题可以结束了吧？

边界条件.......

想当然边界条件就是 dp [ 1 ][ 0 ] 和 dp [ 1 ][ 1 ] 了

所以我们只要来个 dp [ 1 ][ 2 - a [ 1 ] ] = 1；dp [ 1 ][ a [ 1 ] - 1 ] =0；

就能完美的解决 a [ 1 ] = 1 或 2 的赋值情况了qwq

好了，下面上 AC 代码：

#include<iostream>
#include<cstdio>
#include<math.h>
#include<cmath>
using namespace std;
int n,a[],dp[][]; //a数组存放每头奶牛的编号，dp数组来求第i头奶牛改成1或2所用的最少次数
int main()
{
cin>>n;
for(int i=; i<=n; i++) cin>>a[i];
dp[][a[]-]=; //完美得处理了a[1]=1或2的不同情况
dp[][-a[]]=;
for(int i=; i<=n; i++)
{ //从2开始，因为1我们已经处理了
if(a[i]==)
{ //分类讨论
dp[i][]=dp[i-][]; //重点的转移方程，没看懂请看上面详细解析
dp[i][]=min(dp[i-][],dp[i-][])+;
}
if(a[i]==)
{
dp[i][]=dp[i-][]+; //与a[i]==1类似
dp[i][]=min(dp[i-][],dp[i-][]);
}
}
cout<<min(dp[n][],dp[n][]); //输出最小值
return ;
}