HDU 4870Rating（推公式）

有关这个题的高斯消元的方法已经在我的另一篇博客中给出http://www.cnblogs.com/gj-Acit/p/3888382.html

这里介绍一个很吊的解法，复杂度降到了O(n)，以下转自http://www.cnblogs.com/chanme/p/3861766.html

先考虑一场比赛的情况，定义dp[k]为当前为k分，要达到20分时的期望回合数。(令q=1-p)

那么显然有 dp[0]=1+p*dp[1]+q*dp[0] 化简得 dp[0]=1/p+dp[1]

dp[1]=1+p*dp[2]+q*dp[0] 化简得 dp[0]=1/p+1/p^2+dp[2]

我们令 dp[0]=tk+dp[k] 那么tk就表示由0状态到达k状态所需的期望回合数。那么显然如果是要到达20分的话，答案就是t20

然后我们看 dp[k]=1+p*dp[k+1]+q*dp[k-2] 代入dp[0]=dp[k]+tk 就有

dp[0]=1/p+1/p*t[k]-(1-p)/p*t[k-2]+dp[k+1]

所以 t[k+1]＝1/p+1/p*t[k]-(1-p)/p*t[k-2]

边界条件是 t[0]=0,t[1]=1/p,t[2]=1/p+1/p^2

知道这些就可以递推出所有需要的t[k]了。

现在我们来看如果有两个账号怎么破。首先我们必然是（0,0）->(0,1)->(1,1)->(1,2)->(2,2)－>(2,3)->(3,3)...

(0,0)->(0,1)需要的期望回合数是t[1]-t[0]. (0,1)->(1,1)需要的期望回合数是 t[1]-t[0]

(1,1)->(1,2)需要的期望回合数是t[2]-t[1]. (1,2)->(2,2)需要的期望回合数是 t[2]-t[1].

....

(18,18)->(18,19)需要的期望回合数是t[19]-t[18]. (18,19)->(19,19)需要的期望回合数是t[19]-t[18].

(19,19)->(19,20)需要的期望回合数是t[20]-t[19]。

全部加起来的结果就是t[19]*2+t[20]-t[19].

所以最后的复杂度可以是线性的，而且理论上对于k个账号也是适用的，这样就可以避开了高斯消元的做法了。

好吊，体会到了退公式的重要性了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF ((LL)100000000000000000)

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 double t[];

 int main()

 {

     //FOPENIN("in.txt");

     double p;

     while(~scanf("%lf", &p))

     {

         t[] = ;

         t[] =  / p;

         t[] =  / p +  / p / p;

         for(int i=;i<=;i++)

         {

             t[i] =  / p * t[i-] +  / p - (-p) / p * t[i-];

         }

         double ans =  *t[] + t[] - t[];

         printf("%lf\n", ans);

     }

     return ;

 }

巴特西

HDU 4870Rating（推公式）

最新文章

热门文章