首页 > 试题广场 > 游游的旅行
[编程题]游游的旅行
  • 热度指数:413 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解


游游和小伙伴结伴而行,途径一处园林,游游与小伙伴决定进去游览。该园林可以看作一张个点(每个点代表一个景点)条边的无向图(无重边,无自环)。旅途中,两人的初始愉悦度皆为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 回复(3)
#include <bits/stdc++.h>
using namespace std;

const int N = 101;
struct P{
    int id, t;
};
int n,m,k;
vector<P> G[N];
vector<int> M(N), v1(N), v2(N);

double F(vector<int> v){
    double dp[n+1][k+1];
    memset(dp, 0, sizeof(dp));
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n;i++){
            double s = 0;
            int cnt = 0;
            if(j>=M[i])
                dp[i][j] += v[i];
            for(int u=0;u<G[i].size();u++)
                if(j>=G[i][u].t + M[i] + M[G[i][u].id]){
                    s += dp[G[i][u].id][j-G[i][u].t-M[i]];
                    cnt++;
                }
            if(s)
                dp[i][j] += s/cnt;
        }
    double r = 0;
    for(int i=1;i<=n;i++)
        r += dp[i][k];
    return r / n;
}

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>M[i]>>v1[i]>>v2[i];
    }
    int x,y,t;
    for(int i=0;i<m;i++){
        cin>>x>>y>>t;
        G[x].push_back({y, t});
        G[y].push_back({x, t});
    }
    printf("%.5f %.5f\n", F(v1), F(v2));
    return 0;
}

发表于 2020-01-10 12:31:11 回复(0)
double getNum(vector<int>& v) {
    vector<vector<double>> dp(n + 1, vector<double>(k + 1, 0));
    //dp[i][j]表示到达i景点的时候,游玩时间还有j分钟愉悦值的期望
    for (int j = 1; j <= k; ++j) {
        for (int i = 1; i <= n; ++i) {
            if(j>=mi[i])dp[i][j] += v[i];//时间够访问i景点的话,则加上i景点的愉悦值
            double sum = 0;
            int x = 0;
            for (int q = 0; q < G[i].size(); ++q) {
                if (j >= G[i][q].second + mi[i] + mi[G[i][q].first]) {
                    sum += dp[G[i][q].first][j - G[i][q].second - mi[i]];
                    x++;
                    //当时间够访问当前i节点,并能够抵消访问相邻节点的时间和到达相邻节点之和的时候
                    //从相邻节点出发,并更新剩余时间。
                }
            }
            if (sum)dp[i][j] += sum / x;//sum为从当前i景点到所有可以达到并来得及游玩的愉悦值之和,x为满足条件的景点个数
        }
    }
    double ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += dp[i][k];//开始的n个节点是随机获取的,不考虑时间够不够,所以期望直接除以n;
    }
    return ans / n;
}
编辑于 2019-11-08 09:36:04 回复(0)