CodeForces - 714E + POJ - 3666 (dp严格单调递增与非严格单调递增)
2024-09-05 19:28:16
左偏树
炒鸡棒的论文《左偏树的特点及其应用》
虽然题目要求比论文多了一个条件,但是……只需要求非递减就可以AC……数据好弱……
虽然还没想明白为什么,但是应该觉得应该是这样——求非递减用大顶堆,非递增小顶堆……
这题和bzoj1367题意差不多,但是那题求的是严格递增。(bzoj找不到那道题,可能是VIP或什么原因?
严格递增的方法就是每一个数字a[i]都要减去i,这样求得的b[i]也要再加i,保证了严格递增(为什么对我就不知道了
代码比较水,因为题目数据的问题,我的代码也就钻了空子,反正ac就好了。。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = ;
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 = ;
tr[cnt_tr].sz = ;
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 + ;
tr[x].sz = tr[tr[x].l].sz + tr[tr[x].r].sz + ;
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 = ;
for (int i = ; i < n; ++i) {
scanf("%d", a+i);
sum += a[i];
}
int cnt = ;
for (int i = ; i < n; ++i) {
root[++cnt] = NewTree(a[i]);
num[cnt] = ;
while (cnt > && Top(root[cnt]) < Top(root[cnt-])) {
cnt--;
root[cnt] = Merge(root[cnt], root[cnt+]);
num[cnt] += num[cnt+];
while (tr[root[cnt]].sz* > num[cnt]+) Pop(root[cnt]);
}
}
int px = ;
for (int i = ; i <= cnt; ++i)
for (int j = , x = Top(root[i]); j < num[i]; ++j)
tmp += abs(a[px++]-x);
ans = tmp; printf("%lld\n", ans);
}
return ;
}
----
考虑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 <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int N = ;
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 = ; i <= n; ++i) {
scanf("%d", a+i);
b[i] = a[i];
}
sort(b+, b++n);
int last;
for (int i = ; i <= n; ++i) {
last = INF;
for (int j = ; j <= n; ++j) {
last = min(last, dp[i-][j]);
dp[i][j] = fabs(b[j]-a[i]) + last;
}
}
int ans = INF;
for (int i = ; i <= n; ++i) {
ans = min(ans, dp[n][i]);
} printf("%d\n", ans); return ;
}
贪心
https://blog.csdn.net/lycheng1215/article/details/80089004
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std; const int maxn = 2e5 + ;
int a[maxn]; priority_queue<int>s; int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
long long ans = ;
for(int i = ;i <= n ; i ++) {
scanf("%d", &a[i]);
//a[i] -= i;
s.push(a[i]);
if(s.top() > a[i]){
ans += s.top() - a[i];
s.pop();
s.push(a[i]);
}
}
printf("%d",ans);
return ;
}
单调递增严格就是将a[i] - i 跑 以上就行
最新文章
- Android带加减的edittext
- 【bzoj2073】[POI2004]PRZ
- EasyUI 的Tab 标签添加右键菜单
- DIV相关的操作总结
- 【题解】【DP】【Leetcode】Climbing Stairs
- OpenGL超级宝典第5版&;&;基础渲染
- Unity3D游戏开发——Asset Server搭建
- 关于promise
- ViewPager 滑动一半的判断方法以及左滑右滑判断
- 如何从二维数组中的多个key中获取指定key的值?
- 二维、三维 Laplace 算子的极坐标表示
- C#版 - 剑指offer 面试题9:斐波那契数列及其变形(跳台阶、矩形覆盖) 题解
- 自己制作Chrome便携版实现多版本共存
- java设计模式:概述与GoF的23种设计模式
- Linux svn服务器搭建
- 将你的Vim 打造成轻巧强大的IDE
- SDOI 2018 R2 游记
- SpringMvc中的Interceptor拦截器的学习
- 解决VS2010中工具箱里没有WPM
- Codeforces Round #412 A Is it rated ?