interlinkage:

https://www.luogu.org/problemnew/show/P4563

description:

[JXOI 2018] 守卫 解题报告 (DP) 随笔

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

solution:

  • 注意到对于范围$[l,r]$，$r$这个亭子一定要设置保镖
  • 设$f_{l,r}$为活动范围为$[l,r]$所需的最小保镖数
  • 枚举右端点$r$，然后从右向左遍历左端点$l$。设$p$为在$[l,r]$中$r$处能看到的最左的点
  • 这样的话我们就必须在$p$或者$p-1$处放置保镖
  • 于是$f_{l,r}=min(f_{l,p-1},f_{l,p})+f_{p+1,r}$
  • 注意一下$p$的更新，若$l$到$r$连线的斜率小于$p$到$r$连线的斜率，那么就要更新$p=l$了

code:

#include<algorithm> #include<cstring> #include<cstdio> #include<iostream> #include<cmath>
using namespace std; const int N=5000+15; int n; int h[N],f[N][N]; inline int read() { char ch=getchar();int s=0,f=1; while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return s*f; } double slope(int l,int r) {return (double)(h[r]-h[l])/(r-l);} bool cansee(int l,int p,int r) { return slope(l,r)<slope(p,r); } int main() { n=read(); for (int i=1;i<=n;i++) h[i]=read(); int ans=0; for (int r=1;r<=n;r++) { f[r][r]=1;ans^=f[r][r]; int p=0; for (int l=r-1;l>=1;l--) { if (!p||cansee(l,p,r)) p=l; f[l][r]=min(f[l][p-1],f[l][p])+f[p+1][r]; ans^=f[l][r]; } } printf("%d\n",ans); return 0; }
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄