首页 > 试题广场 > 游游的旅行
[编程题]游游的旅行


游游和小伙伴结伴而行,途径一处园林,游游与小伙伴决定进去游览。该园林可以看作一张个点(每个点代表一个景点)条边的无向图(无重边,无自环)。旅途中,两人的初始愉悦度皆为0 ,第 i个景点需要耗费分钟的时间,会让游游和小伙伴的愉悦度分别增加 。每条边代表一条路径,第 i 条边连接编号为 的两个景点,从走到或者从走到耗费的时间都是分钟。游游和小伙伴预计在该园林停留 分钟。检票进入园林后,游游和小伙伴会等概率的随机选择一个景点开始游览,每游览完一个景点后,游游和小伙伴会等概率的随机选择一个可以从当前景点直达的且来得及玩的景点作为下一个目的地。如果游览完一个景点后周围没有可以直达的且来得及游览的景点,游游和小伙伴就会提前结束游玩。 请分别计算出游游和小伙伴在游览结束后愉悦度的期望。  



输入描述:
第一行三个整数,分别表示, , ,以空格隔开;
接下来的行,每行三个整数,分别表示 ,,以空格隔开;
接下来的行,每行三个整数,分别表示, ,以空格隔开。


输出描述:
输出一行实数,分别表示游游和小伙伴度的期望,精确到小数点后 5位,以空格隔开。
示例1

输入

5 4 60
25 12 83
30 38 90
16 13 70
22 15 63
50 72 18
2 1 7
3 1 7
4 3 1
5 3 10

输出

39.20000 114.40000

备注:
数据范围如下:

普通DP问题
比较坑的一点是,走过的地方还能重复走,这对于旅游来说,也是听奇葩的。。。。
dp[i][j]: 在点i,剩余时间还有j时,两个小伙伴所得到happy值的期望。

代码如下,没什么好说的:

// cont/list1.cpp

#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

vector<vector<int> > mp;
vector<vector<pair<double, double>>> dp;
vector<int> happy1, happy2, times;
int n;
pair<double, double> dfs(int start, int remain)
{
    if(dp[start][remain] != pair<double, double>(0,0))
        return dp[start][remain];
    int cnt = 0;
    for(int to = 1 ; to <= n ; to++)
    {
        if(mp[start][to] > 0 && remain - times[to] - mp[start][to] >= 0)
            cnt += 1;
    }
    pair<double, double> res(0,0), ans(happy1[start],happy2[start]);
    for(int to = 1 ; to <= n ; to++)
    {
        if(mp[start][to] > 0 && remain - times[to] - mp[start][to] >= 0)
        {
            res = dfs(to, remain - times[to] - mp[start][to]);
            ans.first += res.first / cnt;
            ans.second += res.second / cnt;
        }
    }
    dp[start][remain] = ans;
    return ans;
}

int main()
{
    int m,k,x,y,w;
    cin >> n >> m >> k;
    mp.resize(n+1);
    dp.resize(n+1);
    for(int i = 0 ; i < n+1; i++)
    {
        mp[i].resize(n+1);
        dp[i].resize(k);
    }
    happy1.resize(n+1);
    happy2.resize(n+1);
    times.resize(n+1);


    for(int i = 1 ; i <= n ;i++)
        cin >> times[i] >> happy1[i] >> happy2[i];
    for(int i = 0 ; i < m ; i++)
    {
        cin >> x >> y >> w;
        mp[x][y] = w;
        mp[y][x] = w;
    }
    pair<double ,double> now, ans(0.0, 0.0);
    for(int i = 1 ; i <= n ; i++)
    {
        if(k - times[i] < 0)
            continue;
        now = dfs(i, k-times[i]);
        ans.first += now.first / n;
        ans.second += now.second / n;
    }
    printf("%.5f %.5f\n", ans.first, ans.second);
    return 0;
}

"""

发表于 2019-05-14 16:14:40 回复(0)