今天我在翻DP的时候，意外的发现了这个有趣的东西:-D。
其实很简单……只是居然可以用Dp。而且能做的事情很多。
Viterbi可以在给定的HMM状态空间S，初始情况i的概率为πi，状态i到j的转移概率aij。观察结果y1,y2,...yn的情况下，
计算出初始状态序列x1,x2,...,xn最有可能是什么。由于转移是有阶段的，HMM又只考虑i->i+1，所以可以用dp做。
V[t][k]=前t个最终状态为k的情况下，最有可能的观测结果最有可能对应的状态序列的概率。
显然
V[t][k] = P(k|yt) * max{ ax,k * V[t-1][x] }
V[1][k] = P(k|y1) * πk
然后，用一个Ptr记录一下转移的情况就行了……
显然
Ptr[1][k]=0
Ptr[t][k]=argmax{ax,k * V[t-1][x]}
#include <cstdio>
int n,k,t;
int y[110],x[110];
double A[110][110];
double B[110][110];
double P[110];
double V[110][110];
int Ptr[110][110];
int main(){
scanf("%d%d%d",&n,&k,&t);
for (int i = 1; i <= t; i++) scanf("%d",y+i);
for (int i = 1; i <= k; i++)
for (int j = 1; j<= k; j++)
scanf("%lf",&A[i][j]);
for (int i = 1; i <= k; i++)
for (int j = 1; j<= n; j++)
scanf("%lf",&B[i][j]);
for (int i = 1; j<= k; i++) scanf("%lf",P+i);
for (int i = 1; i<= k; i++)
{
Ptr[1][i] = 0;
V[1][i] = P[i] * B[i][y[1]];
}
for (int i = 2; i<= t; i++)
for (int j = 1; j<=k; j++){
double lmax = 0;
for (int l = 1; l<=k; l++){
if (A[l][k]*V[i-1][l] > lmax)
{
lmax = A[l][k]*V[i-1][l];
Ptr[i][j] = l;
}
V[i][j] = lmax * B[j][y[i]];
}
}
double lmax = 0;
for (int i = 1; i<= k; i++)
if (V[t][i]>lmax){
lmax = V[t][i];
x[t] = i;
}
for (int i = t-1; i>=1 ; i++){
x[i] = Ptr[i][x[i+1]];
}
for (int i = 1; i<=t; i++) printf("%d%c",x[i],i==t?'\n':' ');
}
http://zh.wikipedia.org/zh-cn/%E7%BB%B4%E7%89%B9%E6%AF%94%E7%AE%97%E6%B3%95
2019年9月11日 01:05
Dubai Housekeeping can be described as soundly were able cleaning business enterprise in Dubai who understands the unique requirements not to mention culture of this UAE and then the region. Our vacuuming services are introduced from recognizing bother for rendering cleaning experienced and tidy cleaning assistance in Dubai not to mention Abu Dhabi. A lot of our staff are actually carefully particular, well groomed not to mention excellently coached. Staff individuals are tidy in matchups and comprehensively trained concerning modern cleaning begin enlarging deliver superior consistent vacuuming services through Dubai not to mention Abu Dhabi.
2019年11月11日 07:02
One of the important elements in life has been to be healthy--not just simply physically, but at your inner levels and emotionally in addition. Follow all these steps to brew a well-balanced, healthy and balanced life.
2020年3月17日 05:03
It is literally true on the subject of buying your dream house. To be a first-time property buyer, you need to understand where and the best way to begin your house buying practice. The using questions in addition to answers are carefully selected to provide a footing of basic information about home paying for.
2020年3月17日 05:03
But if your home inspector discovers an important problem an increasingly specific Inspection can be recommended. It might be wise to consider taking your home inspected with the presence of a range of health-related pitfalls like radon propane asbestos, or possible difficulty the mineral water or throw away disposal process.
2020年3月17日 05:04
Clean-up cloths will not be the solely cleaning materials which are made having microfiber. If you would like replace all of your current cleaning products with microfiber, chances are you'll do and so. This will make a whole system that won't only get away from your developing looking fresh, but likewise smelling fresh.
2020年3月17日 05:04
Taking your home have a hodgepodge connected with architectural styles is usually off-putting into a potential homebuyer. For some sort of ranch-style property, featuring columns within the front porch is usually just seeing that jarring to be a log-cabin-styled property with skill deco decor.
2020年3月17日 05:06
Begin by thinking about your plight. Are you wanting to buy your dream house? How much would you afford within a monthly house loan payment? How considerably space are you needing? What elements of town will you like? When you finally answer most of these questions, complete a "To Do" list you need to doing relaxed research in relation to property.
2020年4月27日 01:42
The particular maid regarding honor obligations continue till the past minutes with the wedding evening. From preserving the bride far from the groom themselves eyes ahead of the ceremony to making sure the new bride has every one of the necessities ready for the day, the maid of recognize has the girl hands full on the special day. Little information like perhaps the bride gets the wedding aroma, veil, the girl flower lady etc. to ensuring that she just isn't too stressed or hungry ahead of the ceremony, are typical in the particular maid regarding honor's record.
2020年4月27日 01:42
Your home painters must be left to view your position and guide a quotation how much these are charging. You should show them your current exact requirement and become open to just about any suggestion off their end. These are professionals, and having had the opportunity to develop various projects during the past, they include the right individuals to judge whether your requirements can develop the correct type output.
2021年6月06日 00:40
At this moment, if you actually implement every single tips as said before above, it is also possible to sustain a cleanse room and offer your house the latest look. Also, if you require any next help, in that case call Cleaning service Agency Dubai. Professionals currently have immense is vital the cleaning up process and cleaning gear. Thus, you might retain your secure feeling by choosing expert service.
2021年8月31日 21:54
The responsibility of bringing up a child involves struggling with lots in mess. Moms (notably housewives) can be mostly in the midst of messy employment. Sometimes they are really found wiping ones own sticky fingers besides other times they are really sorting because of mental harm. For them all, the effusion of calmness for a few years tends to remain painfully incredibly elusive. For them all, standard home cleaning services can be nothing only a fortunate thing. The moods in moms have been completely observed to evolve for so much the better, once ones own household maintaining work finishes.
2024年1月30日 02:59
Do you know of a family to tend aside from taking good care of the equipment or older folk person? Don't you miss having discretion to you? Are you actually weary of cleaning up every working day? If that you are considering enlisting the assistance of cleaning service personnel, you've taken the first thing to reducing your download by doing a little homework.