程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3640 Hep me Escape 終於有點來感了

ZOJ 3640 Hep me Escape 終於有點來感了

編輯：C++入門知識

此題與其類似，只不過把步數變成了戰斗力。其實這個轉換就像BFS中把無權圖中的步數變成了有權圖的最短路。BFS要搜索的東西變了，但是本質是一樣的。

這裡把步數變成戰斗力，所以要把 dp 的狀態轉移變成戰斗力的轉移。

總之就是什麼變就對什麼構造狀態轉移方程。就像BFS中要找關於哪個變量的最短路就設置關於哪個變量的優先隊列。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

#pragma comment(linker, /STACK:1024000000);
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long int
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 1000000007
#define LM(a,b) (((ULL)(a))<<(b))
#define RM(a,b) (((ULL)(a))>>(b))

const double PI = acos(-1.0);

using namespace std;

int c[110];

double dp[10010];
int t[110];

int main()
{
    int n,f;

    int i,j;

    while(scanf(%d %d,&n,&f) != EOF)
    {

        int Max = 0;

        for(i = 1; i <= n; ++i)
        {
            scanf(%d,&c[i]);

            t[i] = floor((1+sqrt(5.0))*c[i]*c[i]/2.0);

            Max = max(Max,c[i]);
        }

        for(dp[Max+1] = 0,i = 1; i <= n; ++i)
        {
            dp[Max+1] += t[i];
        }

        dp[Max+1] /= n;

        for(i = Max; i >= f; --i)
        {
            dp[i] = 0;

            for(j = 1; j <= n; ++j)
            {
                if(i > c[j])
                {
                    dp[i] += t[j];
                }
                else if(i+c[j] <= Max)
                {
                    dp[i] = dp[i] + dp[i+c[j]] + 1;
                }
                else
                {
                    dp[i] = dp[i] + dp[Max+1] + 1;
                }
            }

            dp[i] /= n;
        }

        printf(%.3lf
,dp[f]);
    }

    return 0;
}