CodeForces714E+POJ3666（dp严格单调递增与非严格单调递增）

#include
#include
#include
#include
using namespace std;const int N &＃61; 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[&＃43;&＃43;cnt_tr].key &＃61; k;tr[cnt_tr].l &＃61; tr[cnt_tr].r &＃61; tr[cnt_tr].dis &＃61; 0;tr[cnt_tr].sz &＃61; 1;return cnt_tr;
}int Merge(int x, int y) {if (!x || !y) return x &＃43; y;if (tr[x] < tr[y]) swap(x, y);tr[x].r &＃61; 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 &＃61; tr[tr[x].r].dis &＃43; 1;tr[x].sz &＃61; tr[tr[x].l].sz &＃43; tr[tr[x].r].sz &＃43; 1;return x;
}int Top(int x) {return tr[x].key;
}void Pop(int &x) {x &＃61; 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 &＃61; sum &＃61; tmp &＃61; 0;for (int i &＃61; 0; i i) {scanf("%d", a&＃43;i);sum &＃43;&＃61; a[i];}int cnt &＃61; 0;for (int i &＃61; 0; i i) {root[&＃43;&＃43;cnt] &＃61; NewTree(a[i]);num[cnt] &＃61; 1;while (cnt > 1 && Top(root[cnt]) 1])) {cnt--;root[cnt] &＃61; Merge(root[cnt], root[cnt&＃43;1]);num[cnt] &＃43;&＃61; num[cnt&＃43;1];while (tr[root[cnt]].sz*2 > num[cnt]&＃43;1) Pop(root[cnt]);}}int px &＃61; 0;for (int i &＃61; 1; i <&＃61; cnt; &＃43;&＃43;i)for (int j &＃61; 0, x &＃61; Top(root[i]); j j)tmp &＃43;&＃61; abs(a[px&＃43;&＃43;]-x);ans &＃61; tmp;printf("%lld\n", ans);}return 0;
}

#include
#include
#include
#include using namespace std;
const int N &＃61; 2005;
const int INF &＃61; 0x5f5f5f5f;int dp[N][N];
int a[N], b[N];
int main() {//freopen("in", "r", stdin);int n;scanf("%d", &n);for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) {scanf("%d", a&＃43;i);b[i] &＃61; a[i];}sort(b&＃43;1, b&＃43;1&＃43;n);int last;for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) {last &＃61; INF;for (int j &＃61; 1; j <&＃61; n; &＃43;&＃43;j) {last &＃61; min(last, dp[i-1][j]);dp[i][j] &＃61; fabs(b[j]-a[i]) &＃43; last;}}int ans &＃61; INF;for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) {ans &＃61; min(ans, dp[n][i]);}printf("%d\n", ans);return 0;
}

#include
#include
#include
#include
using namespace std;const int maxn &＃61; 2e5 &＃43; 7;
int a[maxn];priority_queue<int>s;int main(int argc, char const *argv[])
{int n;scanf("%d", &n);long long ans &＃61; 0;for(int i &＃61; 1;i <&＃61; n ; i &＃43;&＃43;) {scanf("%d", &a[i]);//a[i] -&＃61; i;
s.push(a[i]);if(s.top() > a[i]){ans &＃43;&＃61; s.top() - a[i];s.pop();s.push(a[i]);}}printf("%d",ans);return 0;
}