POJ - 3670 Eating Together——dp，O（n）

POJ - 3670 Eating Together——dp，O（n）

题目大意：给你一串只由1 2 3组成的序列，让你把这个序列变成递增序列或递减序列，且变换次数最少。每次变换你可以把任意一个数变成1、 2、 3

如1 3 2 1 1，你需要把第一个1变成3使得这个序列递减，最小变换次数为1

思路：定义dp[i][j]为长度为i、末元素为j的序列满足条件的最小变换次数，则对于递增序列dp[i][j]可由dp[i-1][1~j]转移而来，对于递减序列dp[i][j]可由dp[i-1][j~3]转移而来。

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 30000 + 10;int a[maxn], dp[maxn][5];int main(){ int n; while (scanf("%d", &n) == 1) { for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int ans = INF; dp[0][1] = dp[0][2] = dp[0][3] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= 3; j++) { dp[i][j] = i; for (int k = 1; k <= j; k++) { dp[i][j] = min(dp[i][j], dp[i - 1][k]); } if (a[i] != j) dp[i][j]++; } } for (int i = 1; i <= 3; i++) ans = min(ans, dp[n][i]); dp[0][1] = dp[0][2] = dp[0][3] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= 3; j++) { dp[i][j] = i; for (int k = 3; k >= j; k--) { dp[i][j] = min(dp[i][j], dp[i - 1][k]); } if (a[i] != j) dp[i][j]++; } } for (int i = 1; i <= 3; i++) ans = min(ans, dp[n][i]); printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。