1 条题解
-
1XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2023-10-11 17:14:42
城市规划(planning)
考虑二分答案,显然想要更小的不美观度一定需要更多的修改次数,所以答案是符合二分性质的,二分之后考虑DP,设\(f[i]\)表示对于前\(i\)座大厦,在第\(i\)栋不修改的情况下满足不美观度条件最少所需修改次数,初始时\(f[i]=i-1\),而这里要求第\(i\)栋不修改是为了方便转移,转移时若\(H_i,H_j\)之间的高度差不超过二分值的\(i-j\)倍,则可以在\(f[j]\)的基础上再修改\(i-j-1\)栋大厦的高度来达成不美观度条件,最后若存在某个\(f[i]+n-i\)不超过\(k\)则说明当前二分值可行
注意这里二分时\(l+r\)可能会超过int
的范围,所以应该使用\((r-1)/2+l\)或者更大范围的类型来进行二分#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<ctime> #include<algorithm> #define MAXN 2005 #define LL long long using namespace std; inline int read() { int num=0,sgn=1; char ch=getchar(); while (ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if (ch=='-')sgn=-1,ch=getchar(); while (ch>='0'&&ch<='9')num*=10,num+=ch-'0',ch=getchar(); return num*sgn; } int n,k,h[MAXN]; int l,r,mid; bool check(int m) { int dp[MAXN]; memset(dp,0,sizeof(dp)); for (int i=1;i<=n;i++) dp[i]=i-1; for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if ((LL)abs(h[i]-h[j])<=(LL)(j-i)*(LL)m) dp[j]=min(dp[j],dp[i]+j-i-1); for (int i=1;i<=n;i++) if (dp[i]+n-i<=k)return 1; return 0; } int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%d",&h[i]); l=0;r=2000000000; while (l<=r) { mid=l+(r-l)/2; if (check(mid))r=mid-1; else l=mid+1; } printf("%d\n",l); return 0; }
- 1
信息
- ID
- 1015
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 16
- 已通过
- 7
- 通过率
- 44%
- 上传者