首先可以明确一个方面，那就是如果将X改成Y，那么Y肯定是这N个数中的某一个（为什么仔细想想） 之后可以得到一个状态转移那就是dp[i][j]代表已经考虑了i位的情况下，结尾为j的最小更改数。 状态转移为dp[i][j] = min(dp[i-1][k] + abs(a[i] - b[j])) 这样的话可以写出一个初步的代码： #include<cstdio>#include<cst

题目地址：POJ3666 dp[i][j]表示第i位时，值为j时的最小代价。因为j太大，由于要改变值的话，变到与之最近的值相同是最优的，所以可以离散化，这样，j对应了各个值得下标。复杂度O(n^2)。 代码如下： #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algor

菜菜的说一下（若有幸被高人看见，请指导），初次学dp，这个题想了好久，不会~上网看了一个思路，看了好久，终于看懂了~ 好笨啊%>_<%   先附此人博客： http://blog.sina.com.cn/s/blog_82a8cba50100tog6.html   题意：输入N, 然后输入N个数，求最小的改动这些数使之成非严格递增即可，要是非严格递减，反过来再求一下就可以了。   看

题目 给出一个长度是 n n n的序列 A A A，构造出一个长度为 n n n的单调不递减序列 B B B，使 ∑ i = 1 n a b s ( A [ i ] − B [ i ] ) \sum_{i=1}^nabs(A[i]-B[i]) ∑i=1n​abs(A[i]−B[i])最小 分析 设 f [ i ] [ j ] f[i][j] f[i][j]表示完成前 i i i个数的构造