首页 > ACM题库 > HDU-杭电 > HDU 4711-Weather-动态规划-[解题报告]HOJ
2015
09-17

HDU 4711-Weather-动态规划-[解题报告]HOJ

Weather

问题描述 :

Hovey Chen is going to Azeroth! "I have reached Darnassus." Hovey told Eliane Su, his girlfriend. Each day, Hovey called Eliane, and told her his feeling at Azeroth. "It’s a good day today. We are going to hunt some Goblin :)" "It’s raining and raining. We can do nothing but sleeping :("
Several days later, Hovey was missing Eliane so much. So he came back to the Earth. He wants to write a travel note for his friends. However, he forgets where he had been! What’s worse, he never told Eliane he route. Luckily, he told Eliane the weather in his everyday report, and Eliane wrote it down on her notebook. Hovey knows the probability he went from one place to another. Given the probability from Darnassus to Booty Bay be p, it means that if Hovey is at Darnassus today, the chance he is going to Booty Bay tomorrow is p. Eliane knows the probability of given place to be in given weather. Now given the first place, and the two probability matrices, can you help Hovey to figure out the route which has the greatest probablity.

输入:

The first line is an integer T, the number of test cases.
In each test cases, the first is three positive integers n, m, w (1 ≤ n ≤ 1000, 1 ≤ m, w ≤ 100). Hovey has stayed in Azeroth for n + 1 days. Days are labeled from 0 to n. The number of places in Azeroth is m. The number of weather conditions in Azeroth is w. Hovey was always at Darnassus in day 0, which is place 0.
Then n integers follow, each is in the range of [0, w - 1]. They are weather conditions from day 1 to n.
Then m lines follow, each containing m numbers. The jth number in the ith line is the probabilty from place i to place j. Places are numbered from 0.
Then m lines follow, each containing w numbers. The jth number in the ith line is the probabilty that place i is in weather condition j. Weather conditions are numbered from 0.

输出:

The first line is an integer T, the number of test cases.
In each test cases, the first is three positive integers n, m, w (1 ≤ n ≤ 1000, 1 ≤ m, w ≤ 100). Hovey has stayed in Azeroth for n + 1 days. Days are labeled from 0 to n. The number of places in Azeroth is m. The number of weather conditions in Azeroth is w. Hovey was always at Darnassus in day 0, which is place 0.
Then n integers follow, each is in the range of [0, w - 1]. They are weather conditions from day 1 to n.
Then m lines follow, each containing m numbers. The jth number in the ith line is the probabilty from place i to place j. Places are numbered from 0.
Then m lines follow, each containing w numbers. The jth number in the ith line is the probabilty that place i is in weather condition j. Weather conditions are numbered from 0.

样例输入:

1
3 3 2
1 1 0
0.3 0.5 0.2
0.1 0.2 0.7
0.3 0.3 0.4
0.6 0.4
0.4 0.6
0.3 0.7

样例输出:

1 2 0

题目

比赛

题意:

有m座城市w种天气,已知每天从城市i到城市j的概率,和每座城市每种天气的概率。已知n天的行程每天的天气,求最有可能的这n天每天在哪座城市的序列。多组解输出字典序最小的。

题解:

直接DP,一天天枚举从i到j地转移。由于n最大1000,直接乘精度受不了,最好取log,并且注意概率为0时返回结果为nan,所以自己手动设一个-INF吧。

比赛时3个人读题都看到了旅行了n+1天,并且第一天所在位置是固定的,但是找了很久都没找到在哪说了。可能是因为当时HDU已经跪了吧,第一次交是在还有一个半小时的时候,等到4点才返回个RE,但是那是所有的status都是0ms0KB的RE。后来剩40分钟的时候又交,一直没结果。所以大家都懒得再想了,想出了也不能交……很神奇的是吃完饭回来一眼就看到题目说了第一天是在第0座城市,加上这句再交果然过了。

//Time:343ms
//Memory:2208KB
//Length:1875B
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
#define MP(x,y) make_pair(x,y)
const int MAXN= 110;
const double EPS = 1e-14;
const double INF = 1e50;

long double dp[1010][MAXN];
int fa[1010][MAXN],ord[1010];
double pm[MAXN][MAXN],pw[MAXN][MAXN];
int main()
{
    //freopen("/home/moor/Code/input","r",stdin);
    int ncase,n,m,w;
    scanf("%d",&ncase);
    while(ncase--)
    {
        scanf("%d%d%d",&n,&m,&w);
        for(int i=0;i<n;++i)    scanf("%d",&ord[i]);
        for(int i=0;i<m;++i)
            for(int j=0;j<m;++j)
            {
                scanf("%lf",&pm[i][j]);
                if(pm[i][j]>EPS)
                    pm[i][j]=log(pm[i][j]);
                else    pm[i][j]=-INF;
            }
        for(int i=0;i<m;++i)
            for(int j=0;j<w;++j)
            {
                scanf("%lf",&pw[i][j]);
                if(pw[i][j]>EPS)
                    pw[i][j]=log(pw[i][j]);
                else    pw[i][j]=-INF;
            }
        for(int i=0;i<m;++i)    dp[n-1][i]=pw[i][ord[n-1]];
        for(int i=n-2;i>=0;--i)
        {
            for(int j=0;j<m;++j)    dp[i][j]=-INF;
            for(int j=0;j<m;++j)
                if(pw[j][ord[i]]>-INF+EPS)
                    for(int k=0;k<m;++k)
                        if(pm[j][k]>-INF+EPS&&dp[i][j]+EPS<dp[i+1][k]+pm[j][k]+pw[j][ord[i]])
                            dp[i][j]=dp[i+1][k]+pm[j][k]+pw[j][ord[i]],fa[i][j]=k;
        }
        int pos=0;
        long double best=-INF;
        for(int i=0;i<m;++i)
            if(best+EPS<dp[0][i]+pm[0][i])
                best=dp[0][i]+pm[0][i],pos=i;
        printf("%d",pos);
        for(int i=0;i<n-1;++i)
            printf(" %d",pos=fa[i][pos]);
        printf("\n");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/tri_integral/article/details/11395583