poj 3666 数组整单调 dp 动态规划

题意：
给 n 个数的数组，现在要求你把数组整理成单调的，增或者减。
每次改变有一个花费 abs（a - b），现在问你最小的花费是多少。
【poj 3666 数组整单调 dp】

解析：
dp[ i ] [ j ] 表示的是前 i 个数，末尾数为 num[ j ] 时，整理成单调数组的最小花费。
这题其实直接一个遍历就能求出不管是整理成单调增，或者单调减了，因为我是枚举 num[ j ] 来搞dp的。
状态转移方程：

for (int i = 1; i < n; i++) { int t = inf; for (int j = 0; j < n; j++) { t = min(t, dp[i - 1][j]); dp[i][j] = t + abs(a[i] - num[j]); } }

最后只要询问 dp [ n - 1 ] [ k ] ，其中 k 为 0 到 n - 1，表示的是用 num[0 ~n - 1] 中的一个数作为单调的结尾的最小花费。更新其中最小的即可。

代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define lson lo, mi, rt << 1 #define rson mi + 1, hi, rt << 1 | 1using namespace std; const int maxn = 2000 + 10; const int inf = 0x3f3f3f3f; const double eps = 1e-8; const double pi = acos(-1.0); const double ee = exp(1.0); int a[maxn]; int num[maxn]; int dp[maxn][maxn]; int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); #endif // LOCAL int n; while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) { scanf("%d", &a[i]); num[i] = a[i]; } sort(num, num + n); memset(dp, 0, sizeof(dp)); for (int i = 1; i < n; i++) { int t = inf; for (int j = 0; j < n; j++) { t = min(t, dp[i - 1][j]); dp[i][j] = t + abs(a[i] - num[j]); } } int ans = inf; for (int i = 0; i < n; i++) { ans = min(ans, dp[n - 1][i]); } printf("%d\n", ans); } return 0; }