题目链接
题解
第二问结论题,好神呐
emmmmm
我们一起去%ydc吧
https://pan.baidu.com/share/link?uk=2651016602&shareid=1490516411
代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar(); }
while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();
return x * f;
}
#define LL long long
#define INF (1e17)
const int maxn = 35007;
int n,dp[maxn];
LL a[maxn],b[maxn],c[maxn],Ans[maxn],sumbe[maxn],sumaf[maxn];
inline int find(int x) {
int l = 1,r = n,ret = 0;
while(l <= r) {
int mid = l + r >> 1;
if(c[mid] <= x)l = mid + 1,ret = mid;
else r = mid - 1;
}
return ret;
}
std::vector<int>vec[maxn];
void solve() {
for(int i = 1;i <= n;++ i)
dp[i] = find(b[i]) + 1,c[dp[i]] = std::min(c[dp[i]],b[i]);
int ans = 0;
for(int i = 1;i <= n;++ i) ans = std::max(ans,dp[i]); b[0] = -INF;
printf("%d
",n - ans); vec[0].push_back(0);
for(int i = 1;i <= n;++ i) {
int u = dp[i] - 1;
for(int j = 0;j < vec[u].size();++ j) {
int v = vec[u][j];if(b[i] < b[v])continue;
sumbe[v - 1] = sumaf[v - 1] = 0;
for(int k = v;k <= i;++ k) sumbe[k] = abs(b[k] - b[v]),sumaf[k] = abs(b[k] -b[i]);
for(int k = v + 1;k <= i;++ k) sumbe[k] += sumbe[k - 1],sumaf[k] += sumaf[k - 1];
for(int k = v;k <= i;++ k)
Ans[i] = std::min(Ans[i],Ans[v] + sumbe[k] - sumbe[v] + sumaf[i] - sumaf[k]);
}
vec[dp[i]].push_back(i);
}
printf("%lld
",Ans[n]);
}
int main() {
n = read();
for(int i = 1;i <= n;++ i) a[i] = read(),b[i] = a[i] - i;
a[++ n] = INF; b[n] = a[n] - n;
for(int i = 1;i <= n;++ i) c[i] = Ans[i] = INF;
solve();
return 0;
}