首页 > 试题广场 >

游游的旅行

[编程题]游游的旅行
  • 热度指数:951 时间限制: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

备注:
数据范围如下:
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;
}
编辑于 2021-07-18 10:20:35 回复(0)

普通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)
还以为不能重复,查了半天都找不到bug
发表于 2022-03-18 23:03:22 回复(0)
import java.util.Arrays;
import java.util.Scanner;


/**
 * f[i][j] 是存储的到了点i, 还剩余j的期望
    参考了楼下的java写法~~ 说实话 我主要是期望不知道可以这么求,笑哭。这玩意说是旅游感觉是怪怪的,一直重复走。
    思路是:记忆化搜索dp == 不过是在图的基础上
       1. 首先是数组建图
       2. 直接一步步看吧都写了注释
 */
public class Main {

    static int idx, n, m, k, N = 3010, M = 4010;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[N];
    static int[] time = new int[N], happy1 = new int[N], happy2 = new int[N];
    static double res1, res2;
    static Node[][] f = new Node[N][M];
    static void add(int a, int b, int c){
        e[idx] = b; w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt(); k = in.nextInt();
        for(int i = 1; i <= n; i ++){
            time[i] = in.nextInt();
            happy1[i] = in.nextInt();
            happy2[i] = in.nextInt();
        }
        Arrays.fill(h, -1);
        for(int i = 1; i <= m; i ++){
            int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
            add(a, b, c); add(b, a ,c);
        }
                 // 上面未知图就建立好了

        for(int i = 1; i <= n; i ++){
            if(k - time[i] < 0) continue; //不能去当前点直接下一个点
            Node t = dfs(i, k - time[i]);  //求出这个点的愉悦度
            res1 += t.x / n;   //期望 要除以n
            res2 += t.y / n;
        }

        System.out.printf("%.5f %.5f", res1, res2);


    }

    static Node dfs(int u, int dis){
        if(f[u][dis] != null)  //这个点已经找过,直接返回,也就是减枝
            return f[u][dis];
        int cnt = 0;

        for(int i = h[u]; i != -1; i = ne[i]){   //记录这个点u开始可以去几个点,这里要满足可以去的条件
            int j = e[i];
            if(dis >= w[i] + time[j]){  //看看能去几个点
                cnt ++;
            }
        }
        Node res = new Node(0, 0);
        Node ans = new Node( happy1[u], happy2[u]);
        for(int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            if(dis >= w[i] + time[j]){ //这个点是可以去的
                res = dfs(j, dis - w[i] - time[j]); //一直递归
                ans.x += res.x / cnt;
                ans.y += res.y / cnt;
            }
        }
        f[u][dis] = ans;  //赋值 记忆化搜索要给他值 然后下次递归碰到这个情况的时候才能减枝
        return ans;  //返回以当前点为u,总花费为dis下的期望值
    }


    static class Node{
        double x, y;
        public Node(double x, double y){
            this.x = x;
            this.y = y;
        }
    }
}

编辑于 2021-08-07 18:31:44 回复(0)