首页 > ACM题库 > HDU-杭电 > HDU 2834-Girl Friend II[解题报告]HOJ
2014
02-17

HDU 2834-Girl Friend II[解题报告]HOJ

Girl Friend II

问题描述 :

After a long time of effort, RoBa still keeps single. He finds that all the girls are so hard to understand. They can become happy in one minute, and then get angry in the next. What’s more, what they do is usually quite different from what they think!

As an algorithmic geek, RoBa builds a probability model to study a girl’s behavior. That is, there are N kinds of inner states for one girl. At the beginning, the girl can be at state i with probability Si. Then at every minute after that, the girl’s state can be changed from state i to state j with probability Pij. Of course, S1+S2+…+SN = 100 (in percent), and for all the i, Pi1+Pi2+…+PiN=100

And that’s still not practical enough. RoBa knows that he cannot see the inner state of a girl directly, but can only see her outer behavior. There are M kinds of behaviors, and when a girl is at state i, she will take behavior k with probability Aik. And again, for all the i, Ai1+Ai2+…+AiM=100

Now, given a sequence of a girl’s outer behavior and all the probabilities describe above (we don’t know how RoBa get them!), can you help him to find out the girl’s most probable inner state sequence?


For example, as the figure above described, RoBa observes a girl for three minutes, and the behavior sequence is laugh -> Silent -> Silent. Then the poor boy wants to guess the girl’s real state. Let’s suppose he make a guess that the girl’s inner state sequence is happy -> sad -> happy. With the probabilities above, he can find its possibility is SHappy * AHappy,Laugh * PHappy,Sad * ASad,Silent * PSad,Happy * AHappy,Silent. So RoBa can calculate the possibility of all the inner state sequence, for example, sad->sad->happy, happy->happy->happy, and so on. Then he just simply picks the sequence with the highest possibility as the answer. Of course, this will cost too much time, so RoBa need a more clever algorithm to achieve the same result.

To be more formally, given a girl’s outer behavior sequence (B1, B2, … BT), it is natural that the possibility of a girl’s inner sequence (C1, C2, … CT) is


Don’t be scared of the formula above, it just describe our intuition precisely. This problem is not such difficult as it seems, believe me .

输入:

There are several test cases in the input.

The first line of each test case contains N and M, (1 <= N, M <= 50), the second line contains N numbers S1, S2, …, SN, that is, the probability of girl’s initial states. Then an N*N matrix follow, whose entry in the i-th row and j-th column is Pij, that is, the probability of the girl’s transition from state i to state j. Then an N*M matrix follow, whose entry in the i-th row and k-th column is Aik, that is, the probability of the girl’s behavior is k when she is at state i. As the definition, the sum of each row of the two matrices is 100, and every entry in the matrices is an integer in the range [0,100]. And the last line begins with an integer T (1 <= T <= 50), indicating the observe time of RoBa, then T integers follow, indicating the girls outer behavior sequence. All the T integers are in the range [1..M].

You can assume the observation sequence is always possible in the input, that is, with probability greater than 0.

输出:

There are several test cases in the input.

The first line of each test case contains N and M, (1 <= N, M <= 50), the second line contains N numbers S1, S2, …, SN, that is, the probability of girl’s initial states. Then an N*N matrix follow, whose entry in the i-th row and j-th column is Pij, that is, the probability of the girl’s transition from state i to state j. Then an N*M matrix follow, whose entry in the i-th row and k-th column is Aik, that is, the probability of the girl’s behavior is k when she is at state i. As the definition, the sum of each row of the two matrices is 100, and every entry in the matrices is an integer in the range [0,100]. And the last line begins with an integer T (1 <= T <= 50), indicating the observe time of RoBa, then T integers follow, indicating the girls outer behavior sequence. All the T integers are in the range [1..M].

You can assume the observation sequence is always possible in the input, that is, with probability greater than 0.

样例输入:

2 2
50 50
50 50
50 50
50 50
50 50
2 1 2

2 2
0 100
50 50
49 51
50 50
50 50
2 1 2

样例输出:

1 1
2 2
Hint
Hint: The first case indicating a rather “random” girl, all the initial states, transition, and behavior are of equal possibility, so the four possible inner state sequences 1-1, 1-2, 2-1, 2-2 are of equal possibility. In the second case, the girl is at state 2 definitely at the beginning. Then there is a little bigger chance to change to state 2 than state 1, so the sequence 2-2 is more possible than 2-1.

# include <stdio.h>
# include <string.h>

# define For(i, n) for(i=0; i<(n); i++)

const int N = 64;

double P[N][N];
double A[N][N];
int out[N];
int t;
double s[N];
int n, m;
double dp[N][N];
double dpx[N][N];
int pre[N][N];
int ppt[N];

void read()
{
 int i, j;
 For(i, n)
 scanf("%lf", &s[i]);
 For(i, n)
 For(j, n)
 scanf("%lf", &P[i][j]);
 For(i, n)
 For(j, m)
 scanf("%lf", &A[i][j]);
 For(i, n)
 {
 s[i] /= 100;
 For(j, n)
 P[i][j] /= 100, A[i][j] /= 100;
 }
 scanf("%d", &t);
 For(i, t)
 scanf("%d", &out[i]);
 For(i, t)
 out[i] -= 1;
}

void doit()
{
 memset(dpx, 0, sizeof(dpx));
 int i, j, k;
 double tmp;
 For(j, n)
 {
 dp[0][j] = s[j];
 dpx[0][j] = dp[0][j] * A[j][out[0]];
 }
 for (i = 1; i < t; i++)
 {
 For(j, n)
 {
 For(k, n)
 {
 tmp = dpx[i - 1][k] * P[k][j] * A[j][out[i]];
 if (tmp > dpx[i][j])
 {
 dpx[i][j] = tmp;
 dp[i][j] = dp[i - 1][k] * P[k][j];
 pre[i][j] = k;
 }
 }
 // printf("%d %d %.4f %.4f\n",i,j,dp[i][j],dpx[i][j]);
 }
 }

}

void pt()
{
 int i;
 int tmp;
 double mx = 0;
 For(i, n)
 if (dpx[t - 1][i] > mx)
 {
 mx = dpx[t - 1][i];
 tmp = i;
 }
 ppt[t - 1] = tmp;
 for (i = n-1; i > 0; i--)
 {
 ppt[i - 1] = pre[i][tmp];
 tmp = ppt[i - 1];
 }
 For(i, t)
 {
 if (i)
 putchar(' ');
 printf("%d", ppt[i] + 1);
 }
 puts("");
}

int main()
{

 while (2 == scanf("%d %d", &n, &m))
 {
 read();
 doit();
 pt();
 }
 return 0;
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  4. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }