传送门
由于 Di 只有 3 种情况，那么就很简单了
f[i][j][0] 表示前 i 个，且第 i 个变成 j 的 递增序列最小修改次数
f[i][j][1] 表示前 i 个，且第 i 个变成 j 的 递减序列最小修改次数
状态转移看代码。
——代码
1 #include <cstdio> 2 #include <iostream> 3 4 const int MAXN = 30001; 5 int n, ans = ~(1 << 31); 6 int a[MAXN], f[MAXN][4][2]; 7 8 inline long long read() 9 16 17 inline int min(int x, int y) 18 21 22 int main() 23 37 for(i = 1; i <= 3; i++) 38 for(j = 0; j <= 1; j++) 39 ans = min(ans, f[n][i][j]); 40 printf("%d\n", ans); 41 return 0; 42 }View Code
上一篇：[luoguP2904] [USACO08MAR]跨河River Crossing（DP）
下一篇：[luoguP2434] [SDOI2005]区间（贪心）
DP
