リングの確率dp(一次)zoj 3329

原題住所:https://vjudge.net/problem/ZOJ-3329
テーマ:
3つのサイコロがあり、それぞれk 1,k 2,k 3面があり、初期点数は0である.第iサイコロの点数は1本のkiから.3つのサイコロを投げる点数がそれぞれa,b,cのとき、点数はゼロになります.そうしないと、点数に3つのサイコロの点数とを加えて、点数>nのときに終わります.サイコロを投げる回数の期待を求めます.
(0<=n<= 500,11,K2,K3<=6,1<=a<=K1,1<=b<=K2,1<=c<=K3)
考え方:
現在の点数をiとし、さらにdp[i]回投げたら点数nに達する
今回投げたポイントをkとする
状態遷移方程式dp[i]=Σ(dp[i+k]*p[k])+dp[0]*p[0]+1を書き出しやすくする
現在の状態から、もう一度(これが式中+1の由来である)投げて到達可能な点数はk種あるので、確率はそれぞれp[1]からp[k](もちろん、p[1]、p[2)が0に初期化する.
それ以外にもk 1=a,k 2=b,k 3=cの組み合わせを投げることもあるので、dp[0]*p[0]を加える.
 
これで転移方程式を得た
しかし、実際には使えないことがわかります
一般的に使用できる方程式は,必ずある方向から別の方向に進むか,小さいから大きい(正の)か,大きいから小さい(逆の)かである.
しかしこの方程式では,右の項はiより大きい(dp[i+k])とiより小さい(dp[0])を同時に含んでいる.
これによりdpは自己依存ループに陥る
 
一般的にこのような状況に遭遇すると,Gauss消元法解方程式を用いて解決する.
でもブロガーは料理が多すぎて、まだできません(補うことができて、補うことができます......)
同時に,この問題で我々のdpを阻害するのはdp[0]という項目だけである.
そこでdp[0]を未知数にする方法を採用した.
　　
各dp[i]には同じ要素dp[0]が含まれていることに留意されたい.
dp[i]はdp[0]の線形組合せである(dp[0]の高次べき乗が現れないため)
したがって,遷移方程式をdp[i]=dp[0]*a[i]+b[i]・・・(1)と書くことができる.
そこでdp[i+k]=dp[0]*a[i+k]+b[i+k]
この式を元の遷移方程式に持ち込んでdp[i]=dp[0]*p[0]+Σ(dp[i+k]*p[i+k])+1を得る
さらにこの式中のdp[0]を分離し,式(1)と同様の形式にするdp[i]=dp[0]*(Σ(a[i+k]*p[i+k])+p[0]+(Σ(b[i+k]*p[i+k])+1)
私たちは(1)式を引っ張って、あなたにもっとはっきり見えるようにします:dp[i]=dp[0]*a[i]+b[i]
そこで,a,bに関する新しい方程式を得た.
　　
　　　　a[ i ] = ∑ (   a[ i+k ] * p[ i+k ] ) + p[ 0 ]
               b[ i ] =∑ (  b[ i+k ] * p[ i+k ] ) + 1
 
これは2つの状態遷移方程式であることを驚きました!
a[0]とb[0]を逆プッシュで得ることができる.
式(1)を覚えていますか.iを0にすると、次のようになります.
　　　　　　dp[ 0 ] = dp[ 0 ] * a[ 0 ]+b[ 0 ]
やっとdp[0]を解くことができた
これが本題の答えです
 
下にkuagnbinの大きなコードを添付します.
·　　

#include
#include<string.h>
#include
#include
using namespace std;

double A[600],B[600];
double p[100];
int main()
{
    int T;
    int k1,k2,k3,a,b,c;
    int n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
        double p0=1.0/k1/k2/k3;
        memset(p,0,sizeof(p));
        for(int i=1;i<=k1;i++)
          for(int j=1;j<=k2;j++)
            for(int k=1;k<=k3;k++)
              if(i!=a||j!=b||k!=c)
                p[i+j+k]+=p0;
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        for(int i=n;i>=0;i--)
        {
            A[i]=p0;B[i]=1;
            for(int j=1;j<=k1+k2+k3;j++)
            {
                A[i]+=A[i+j]*p[j];
                B[i]+=B[i+j]*p[j];
            }
        }
        printf("%.16lf
",B[0]/(1-A[0]));
    }
    return 0;
}

 
ブロガーは初心者で、いいと思いますが、いいと思いますか?
よく書けないところもあると思いますので、ご指摘ください.すぐに修正します.