2015
09-17

# 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

//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;
}