题解 P2612 【[ZJOI2012]波浪】

· · 题解

如题： 阿米巴和小强是好朋友。

阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮，他兴奋地叫个不停。而阿米巴则很淡定，他回想起曾经的那些日子，事业的起伏，情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来，简直什么都不算。

于是，这对好朋友不可避免地产生了分歧。为了论证自己的观点，小强建立了一个模型。他海面抽象成一个1到N的排列P[1…N]。定义波动强度等于相邻两项的差的绝对值的和，即：

L = | P2 – P1 | + | P3 – P2 | + … + | PN – PN-1 | 给你一个N和M，问：随机一个1…N的排列，它的波动强度不小于M的概率有多大？

答案请保留小数点后K位输出，四舍五入。 还有： N = 3的排列有6个：123，132，213，231，312，321；他们的波动强度分别为2，3，3，3，3，2。所以，波动强度不小于3的概率是4/6，即0.667。

你也可以通过下面的代码来验证这个概率：

nt a[3]={0,1,2},s=0,n=3;
for (int i=0;i<1000000;i++){
random_shuffle(a,a+n);
int t=0;
for (int j=0;j<n-1;j++) t+=abs(a[j+1]-a[j]); 
if (t>=3) s++;
}
printf("%.3f\n",s/1000000.0);

所以，我们可以这样做： 代码如下

#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;

namespace db{long double dp[2][110][10010][3];}
namespace flt{__float128 dp[2][110][10010][3];}
int N , M , K;

template < class T >

void out(T ans){
        if(ans + 1e-14 >= 1){cout << "1." << string(K,'0') << endl; return;}
    cout << "0.";
    ans *= 10;
    for(int i = 1 ; i <= K ; ++i){
        cout << (int)(ans + (K == i) * 0.5);
        ans = (ans - (int)ans) * 10;
    }
}

template < class T >

inline void solve(T dp[][110][10010][3]){
    T ans = 0;
    dp[0][0][5000][0] = 1;
    int now = 0;
    for(int i = 1 ; i <= N ; ++i){
        now ^= 1;
        memset(dp[now] , 0 , sizeof(dp[now]));
        for(int j = 0 ; j < i ; ++j)
            for(int k = 0 ; k <= 10000 ; ++k)
                for(int p = 0 ; p <= 2 ; ++p)
                    if(dp[now ^ 1][j][k][p]){
                        if(k - 2 * i >= 0)
                            dp[now][j + 1][k - 2 * i][p] += dp[now ^ 1][j][k][p] * (j + 1 - p) / i;
                        if(j)
                            dp[now][j][k][p] += dp[now ^ 1][j][k][p] * (j * 2 - p) / i;
                        if(j >= 2 && k + 2 * i <= 10000)
                            dp[now][j - 1][k + 2 * i][p] += dp[now ^ 1][j][k][p] * (j - 1) / i;
                        if(p != 2){
                            if(k - i >= 0)
                                dp[now][j + 1][k - i][p + 1] += dp[now ^ 1][j][k][p] * (2 - p) / i;
                            if(j && k + i <= 10000)
                                dp[now][j][k + i][p + 1] += dp[now ^ 1][j][k][p] * (2 - p) / i;
                        }
                    }
    }
    for(int i = M ; i <= 5000 ; ++i)
        ans += dp[now][1][5000 + i][2];
    out(ans);
}

int main(){
    cin >> N >> M >> K;
    if(K <= 8)
        solve(db::dp);
    else
        solve(flt::dp);
    return 0;
}

请勿抄袭，后果自负！！！