noi.ac #531 神树和物品
题目链接：戳我
决策单调性
（蒟蒻终于会写决策单调性啦！考试全场切这题就我不会啊嘤）
（证明？不会啊，自己打表看QAQ）
44pts \(O(n^2)\)代码：
#include
#include
#include
#include
#include
#define MAXN 1010
using namespace std;
int n;
long long a[MAXN],b[MAXN],c[MAXN],f[MAXN];
inline long long pow3(long long x){return 1ll*x*x*x;}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
for(int i=0;i<=n;i++) f[i]=0x3f3f3f3f3f3f3f3f;
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j 100pts代码：时间复杂度\(O(nlogn)\)（貌似跑的挺快的hhh）
#include
#include
#include
#include
#include
#define MAXN 300010
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n;
int a[MAXN],b[MAXN],c[MAXN];
struct Node{int pos,l,r;}q[MAXN<<1];
long long f[MAXN];
inline long long calc(int l,int r)
{
long long cur_ans=1ll*(a[r]-b[l+1])*(a[r]-b[l+1])*(a[r]-b[l+1]);
return f[l]+abs(cur_ans)+1ll*c[l+1]*c[l+1]*c[l+1];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
for(int i=1;i<=n;i++) c[i]=read();
int head=1,tail=1;
q[head]=(Node){0,1,n};
for(int i=1;i<=n;i++)
{
while(head>1;
if(calc(i,mid)<=calc(q[tail].pos,mid)) cur_ans=mid,r=mid-1;
else l=mid+1;
}
if(cur_ans!=q[tail].l) q[tail].r=cur_ans-1;
else tail--;
if(cur_ans<=n) q[++tail]=(Node){i,cur_ans,n};
}
printf("%lld\n",f[n]);
return 0;
}