首页 > 代码库 > 【BZOJ1011】【HNOI2008】遥远的行星 根据所允许的误差进行模糊DP
【BZOJ1011】【HNOI2008】遥远的行星 根据所允许的误差进行模糊DP
题解:
暴力肯定过不了,
但是我们可以把除数模糊化一下,让一部分数统一用一个除数,这样就可以在5%误差以内快速出解了。
额,但是前面一大段的动规值需要暴力求,要不就很难满足5%了。。
给个神博客http://hi.baidu.com/zeonsgtr/item/789da6f2838a3dc742c36ab7
再贴个代码
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> #define N 101000 #define eps 1e-7 #define LL long long using namespace std; int n; LL m[N],sum[N]; double a,F[N]; int main() { // freopen("test.in","r",stdin); scanf("%d%lf",&n,&a); for(int i=1;i<=n;i++)scanf("%lld",&m[i]),sum[i]=sum[i-1]+m[i]; for(int i=min(n,2000);i>=1;i--)// 暴力求出前面的f值 { int k=(int)(a*i); if(fabs((double)(k+1)/a-i)<eps)k++; for(int j=1;j<=k;j++)F[i]=F[i]+m[i]*m[j]/(double)(i-j); } for(int i=2001;i<=n;i++) // 因为题目允许有小误差,所以我们可以把一些除数来近似一下。 { int k=(int)(a*i),mid=(1+k)>>1; F[i]=sum[k]*m[i]/(double)(i-mid); } for(int i=1;i<=n;i++)printf("%lf\n",F[i]); return 0; }
【BZOJ1011】【HNOI2008】遥远的行星 根据所允许的误差进行模糊DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。