左偏树
炒鸡棒的论文
虽然题目要求比论文多了一个条件，但是……只需要求非递减就可以AC……数据好弱……
虽然还没想明白为什么，但是应该觉得应该是这样——求非递减用大顶堆，非递增小顶堆……
这题和bzoj1367题意差不多，但是那题求的是严格递增。（bzoj找不到那道题，可能是VIP或什么原因？
严格递增的方法就是每一个数字a[i]都要减去i，这样求得的b[i]也要再加i，保证了严格递增（为什么对我就不知道了
代码比较水，因为题目数据的问题，我的代码也就钻了空子，反正ac就好了。。。。
#include#include #include #include using namespace std;const int N = 2005;typedef long long ll;struct LTree { int l, r, sz; int key, dis; bool operator<(const LTree lt) const { return key < lt.key; }} tr[N];int cnt_tr;int NewTree(int k) { tr[++cnt_tr].key = k; tr[cnt_tr].l = tr[cnt_tr].r = tr[cnt_tr].dis = 0; tr[cnt_tr].sz = 1; return cnt_tr;}int Merge(int x, int y) { if (!x || !y) return x + y; if (tr[x] < tr[y]) swap(x, y); tr[x].r = Merge(tr[x].r, y); if (tr[tr[x].l].dis < tr[tr[x].r].dis) swap(tr[x].l, tr[x].r); tr[x].dis = tr[tr[x].r].dis + 1; tr[x].sz = tr[tr[x].l].sz + tr[tr[x].r].sz + 1; return x;}int Top(int x) { return tr[x].key;}void Pop(int &x) { x = Merge(tr[x].l, tr[x].r);}int a[N], root[N], num[N];int main() { int n; while (~scanf("%d",&n)) { ll sum, tmp, ans; cnt_tr = sum = tmp = 0; for (int i = 0; i < n; ++i) { scanf("%d", a+i); sum += a[i]; } int cnt = 0; for (int i = 0; i < n; ++i) { root[++cnt] = NewTree(a[i]); num[cnt] = 1; while (cnt > 1 && Top(root[cnt]) < Top(root[cnt-1])) { cnt--; root[cnt] = Merge(root[cnt], root[cnt+1]); num[cnt] += num[cnt+1]; while (tr[root[cnt]].sz*2 > num[cnt]+1) Pop(root[cnt]); } } int px = 0; for (int i = 1; i <= cnt; ++i) for (int j = 0, x = Top(root[i]); j < num[i]; ++j) tmp += abs(a[px++]-x); ans = tmp; printf("%lld\n", ans); } return 0;}
这题DP也很神奇，挖坑，明天学……
－－－－
考虑dp，dp[i][j]表示前i个数，最后一个数是j的最小花费
dp方程：dp[i][j]=min(dp[i-1][k], k≤j) ＋ abs(a[i]-j)
j的范围1e9，是因为对于每一个i来说，当最优解的时候j一定是a数列中的数，所以只需枚举a数列中的值就可以了。
容易想到dp[i-1][k]就不需要另外一层循环就了，同时可以使用滚动数组（不使用明显也够
上面求的是不减，求不增把数组到倒过来就可以了。（懒，没写。。
时间复杂度O(n^2)，比上面左偏树明显慢了不少。
#include#include #include #include using namespace std;const int N = 2005;const int INF = 0x5f5f5f5f;int dp[N][N];int a[N], b[N];int main() { //freopen("in", "r", stdin); int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", a+i); b[i] = a[i]; } sort(b+1, b+1+n); int last; for (int i = 1; i <= n; ++i) { last = INF; for (int j = 1; j <= n; ++j) { last = min(last, dp[i-1][j]); dp[i][j] = fabs(b[j]-a[i]) + last; } } int ans = INF; for (int i = 1; i <= n; ++i) { ans = min(ans, dp[n][i]); } printf("%d\n", ans); return 0;}