目录
BZOJ3156 防御准备题解ｃｏｄｅ
BZOJ3156 防御准备
题目传送门
题解
这道\(Dp\)题目也算是比较清真了吧，看到数据范围其实就差不多可以知道是个斜率优化\(Dp\)了。我们比较容易地可以写出转移方程：\(dp[i]=max(dp[j]+\sum_{k=j+1}^{i-1}(i-k))+a[i] \Rightarrow dp[i]=max(dp[j]+\sum_{k=j+1}^{i-1}i-\sum_{k=j+1}^{i-1}k)+a[i])\) \(\Rightarrow dp[i]=max(dp[j]+(i-j-1)*i+\frac{(j+i)*(i-j-1)}{2})\)。然后还是像斜率优化\(Dp\)一样，我们列出不等式：
\(dp[j]+(i-j-1)*i+\frac{(j+i)*(i-j-1)}{2}\geq dp[k]+(i-k-1)*i+\frac{(k+i)*(i-k-1)}{2}\)（
\(j<k\)并且
\(k\)比
\(j\)要优）
然后整理一下可以得到：
\(\frac{f[k]-f[j]+k^2-j^2+k-j}{2*(k-j)}\leq i\)
之后的事情就十分简单了，套用斜率优化的板子就行了。 话说看了黄学长的博客发现还有把\(a[i]\)反过来读入的方法。。表示有点不理解这个方法啊。。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=1e6+500;
int n;
ll a[maxn],f[maxn];
ll que[maxn],l,r;
/*==================Define Area================*/
double Cal(ll j,ll k) {
return (double)(2*(f[k]-f[j])+k*k-j*j+k-j)/(k-j);
}
int main() {
read(n);
for(int i=1;i<=n;i++) {
read(a[i]);
}
for(int i=1;i<=n;i++) {
while(l<r&&Cal(que[l],que[l+1])<2*i) l++;
int t=que[l];
f[i]=f[t]+(i-t)*(i-t-1)/2+a[i];
while(l<r&&Cal(que[r-1],que[r])>Cal(que[r],i)) r--;
que[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9452891.html
相关资源：JAVA上百实例源码以及开源项目
