[luoguP2896] [USACO08FEB]一起吃饭Eating Together（DP）

传送门

由于 Di 只有 3 种情况，那么就很简单了

f[i][j][0] 表示前 i 个，且第 i 个变成 j 的 递增序列最小修改次数

f[i][j][1] 表示前 i 个，且第 i 个变成 j 的 递减序列最小修改次数

状态转移看代码。

——代码

 #include <cstdio>

 #include <iostream>

 const int MAXN = ;

 int n, ans = ~( << );

 int a[MAXN], f[MAXN][][];

 inline long long read()

 {

     long long x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline int min(int x, int y)

 {

     return x < y ? x : y;

 }

 int main()

 {

     int i, j;

     n = read();

     for(i = ; i <= n; i++) a[i] = read();

     for(i = ; i <= n; i++)

     {

         f[i][][] = f[i - ][][] + (a[i] != );

         f[i][][] = min(f[i - ][][], f[i - ][][]) + (a[i] != );

         f[i][][] = min(f[i - ][][], min(f[i - ][][], f[i - ][][])) + (a[i] != );

         f[i][][] = min(f[i - ][][], min(f[i - ][][], f[i - ][][])) + (a[i] != );

         f[i][][] = min(f[i - ][][], f[i - ][][]) + (a[i] != );

         f[i][][] = f[i - ][][] + (a[i] != );

     }

     for(i = ; i <= ; i++)

         for(j = ; j <= ; j++)

             ans = min(ans, f[n][i][j]);

     printf("%d\n", ans);

     return ;

 }