Bzoj 1049
题意：现在我们有一个长度为$n$的整数序列$A$。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
第一问即经典问题。考虑不严格上升的序列，则为$n-LIS$，(这里的$LIS$为不下降的)
严格上升，则说明$i-j \geq a_i-a_j$，不然这个区间不可能严格上升。
移项，则$i-a_i \geq j-a_j$，那么将原来的$a_i$变为$a_i-i$按照同样方法处理即可。
对于第二问，我们设$f(i)$为$[1,i]$的答案，则
$$
f(i)=\max\limits_{dp(j)+1=dp(i)}(f(j)+w(j+1,i))
$$
那么我们怎么计算$w$呢
我们可以发现对于任意区间$[i,j]$都$\exists k$使得$[i,k]=a_i$, $[k+1,j]=a_j$，并且一定$\exists k$使得其为最优策略
那么对于每个$w$暴力$k$的位置。由于数据随机，所以$i$的的决策点$j$很少，复杂度跑不满
注意代码细节，加上前后最小值最大值方便操作
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MAXN = 35000 + 10, INF = 1e10;
LL n, a[MAXN], b[MAXN], len;
LL dp[MAXN], f[MAXN], cst1[MAXN], cst2[MAXN];
vector<LL > vec[MAXN];
LL abss(LL x) {return x > 0 ? x : -x;}
void clean() {
len = 0;
}
int solve() {
clean();
cin >> n;
for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] -= i;
++n, a[n] = INF;
b[++len] = a[1], dp[1] = 1;
for (LL i = 2; i <= n; ++i) {
if (a[i] >= b[len]) b[++len] = a[i], dp[i] = len;
else {
int pos = upper_bound(b + 1, b + 1 + len, a[i]) - b; // 1 upper_bound
b[pos] = a[i], dp[i] = pos;
}
}
printf("%lld\n", n - len);
a[0] = -INF;
vec[0].push_back(0);
for (LL i = 1; i <= n; ++i) {
f[i] = INF;
for (LL j = 0; j < (LL)vec[dp[i] - 1].size(); ++j) {
LL v = vec[dp[i] - 1][j];
if (a[v] > a[i]) continue ;
cst1[v - 1] = cst2[v - 1] = 0;
for (LL k = v; k <= i; ++k) cst1[k] = abss(a[k] - a[v]), cst2[k] = abss(a[k] - a[i]);
for (LL k = v + 1; k <= i; ++k) cst1[k] += cst1[k - 1], cst2[k] += cst2[k - 1];
for (LL k = v; k <= i; ++k) {
LL now = cst1[k] - cst1[v] + cst2[i] - cst2[k];
f[i] = min(f[i], f[v] + now);
}
}
vec[dp[i]].push_back(i);
}
printf("%lld\n", f[n]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
5
1 2 4 3 1
*/
