BZOJ 1011 HNOI2008 遙遠的行星 遞推

BZOJ 1011 HNOI2008 遙遠的行星 遞推

題目大意：給定一條直線上的一些行星，按照題目要求計算，求每個點所受重力

我沒有在標題上寫”亂搞“的原因是我看了題解一堆說亂搞的0.0 然後我就真亂搞了0.0 每個點只計算臨近的1000個，結果狂WA不止。。。

亂搞肯定過不去 不用想了

其實說是遞推比較合適 詳細題解見http://hi.baidu.com/zeonsgtr/item/789da6f2838a3dc742c36ab7 我不累述了

#include
#include
#include
#include
#define M 100100
using namespace std;
int n,t=100,g[M];
double a,mass[M],ans[M];
int main()
{
    int i,j;
    cin>>n>>a;
    for(i=1;i<=n;i++)
    {
        scanf("%lf",&mass[i]);
        g[i]=min(static_cast(i*a+1e-7),n);
    }
    for(i=1;i<=n;i++)
    {
    	if(i<=t)
    	{
			for(j=g[i];j;j--)
          	  ans[i]+=mass[i]*mass[j]/(i-j);
		}
		else
		{
        	ans[i]=mass[i]*ans[i-t]/mass[i-t]*(i-t-g[i-t]/2)/(i-g[i-t]/2);
        	for(j=g[i];j>g[i-t];j--)
        		ans[i]+=mass[i]*mass[j]/(i-j);
		}
    }
    for(i=1;i<=n;i++)
        printf("%.6lf\n",ans[i]);
}