HDU 4624 Endless Spin(cljカウントppt)

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=4624 标题:全部でn個のボールがあって、毎回ランダムに1段の区間を選んで黒く染め(各区間が選択される確率は同じ)、何回すべてのボールが黒く染められることを期待します.
分析:pptでは明らかですが、この問題が最も素晴らしい点は第一歩だと思います.
期待回数=Σi=1∞p[i]
を選択します.
p[i]はi回以降も白球が存在する確率である.
この公式はどうやって来ましたか.直観的な理解としては,現在白球が存在する場合,必ず1回染めなければならないが,今回全体に期待される寄与はp[i]である.その後は従来の処理方法であり,どの球が白球であるかを列挙すると,黒染め可能な区間は固定されているが,その中で繰り返し計算されるため,奇数個の白球の場合に偶数個の白球を減算するだけのシナリオ数が合計シナリオ数であり,この反発法は後のSubstring Pairsの問題にも現れている.
また、この問題は15桁の小数を残し、javaで通過しなければならない.
JAvaはファイルの読み書きを行い、Printwriterを使って書くことができますが、closeを覚えておいてください.
JAvaはprintfを便利に使用できます.
JAvaのBigDecimalでdivide操作を行う場合、scaleと丸めmodeを設定します
Javaコードを添付

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
public class Main
{
        public static void main(String[] args) throws FileNotFoundException 
        {
            File fp2=new File("/home/poursoul/J.out");
            PrintWriter cout=new PrintWriter(fp2);
            Long [][][]dp=new Long[55][2500][2];
            BigDecimal []rep=new BigDecimal[100];
            for(int i=0;i<60;i++)rep[i]=new BigDecimal("0");
            for(int i=0;i<55;i++)for(int j=0;j<2500;j++)for(int k=0;k<2;k++)dp[i][j][k]=new Long(0);
            dp[0][0][0]=(long)1;
            BigDecimal t1=new BigDecimal("1");

            for(int i=1;i<=51;i++)
            {
                for(int j=0;j1)/2;j++)
                {
                    for(int k=0;k<2;k++)
                    {
                        for(int ni=0;niint tot=i-ni-1;
                            tot=tot*(tot+1)/2;
                            if(j>=tot)
                               dp[i][j][k]+=dp[ni][j-tot][k^1];
                        }
                    }
                    Long tp=(long)i*(i-1)/2;
                    BigDecimal p=new BigDecimal(j).divide(new BigDecimal(tp.toString()), 50, BigDecimal.ROUND_HALF_UP);
                    Long tp2=dp[i][j][1]-dp[i][j][0];
                    rep[i-1]=rep[i-1].add(t1.divide(t1.subtract(p), 50, BigDecimal.ROUND_HALF_UP).multiply(new BigDecimal(tp2.toString())));
                }
               dp[i][i*(i-1)/2][0]=new Long(1);
            }
            for(int n=1;n<=50;n++)
                cout.printf("\"%.15f\",
",rep[n]);
            cout.close();
        }
}