数学|【Contra】矩阵乘法优化 dp 数学|tsinsen

偶然间，chnlich发现了他小时候玩过的一个游戏“魂斗罗”，于是决定怀旧。但是这是一个奇怪的魂斗罗MOD。有N个关卡，初始有Q条命。每通过一个关卡，会得到u分和1条命，生命上限为Q。其中u=min(最近一次连续通过的关数,R)。若没有通过这个关卡，将会失去1条命，并进入下一个关卡。当没有生命或没有未挑战过的关卡时，游戏结束，得到的分数为每关得到的分数的总和。由于chnlich好久不玩这个游戏了，每条命通过每个关卡的概率均为p(0<=p<=1)，原先chnlich的最高分纪录是S。现在chnlich想要知道，当p至少为多少时，chnlich期望获得的总分数能够超过原先的最高分。
矩阵乘法优化的dp。
g[i+1][min(j+1,R)][min(k+1),Q]+=g[i][j][k]*p
g[i+1][0][k-1]+=g[i][j][k]*(1-p)
Answer+=g[i][j][k]*p*(j+1)

#include #include #include #include #include #include #define Rep(i, x, y) for (int i = x; i <= y; i ++) using namespace std; const int N = 40; typedef long long LL; typedef double Mtr[N][N]; int p[7][25], n, R, Q, S, m; double d; Mtr A, B, a, b; void Mul(Mtr &a, Mtr b) { Mtr c; memset(c, 0, sizeof(c)); Rep(i, 1, n) Rep(j, 1, n) Rep(k, 1, n) c[i][j] += a[i][k] * b[k][j]; Rep(i, 1, n) Rep(j, 1, n) a[i][j] = c[i][j]; } bool Check(double P) { memset(a, 0, sizeof(a)), n = 0; memset(b, 0, sizeof(b)); Rep(i, 0, Q) { int k = (i == Q) ? R : min(i-1, R); Rep(j, 0, max(k, 0)) p[i][j] = ++ n; } a[1][1] = 1; Rep(i, 1, Q) { int k = (i == Q) ? R : min(i-1, R); Rep(j, 0, max(k, 0)) { int x = p[i][j], y = p[i-1][0], z = p[min(i+1, Q)][min(j+1, R)]; if (i > 1) a[x][y] = (1 - P); a[x][z] = P, a[x][1] = P * min((j + 1), R); } } Rep(i, 1, n) b[i][i] = 1; int y = m; while (y) { if (y & 1) Mul(b, a); Mul(a, a), y /= 2; } return b[p[Q][0]][1] > S; } int main() { scanf ("%d%d%d%d", &m, &R, &Q, &S); int l = 0, r = 10000000, d = r; if (!Check(1)) { puts("Impossible."); return 0; } while (l < r) { int mid = (l + r) / 2; double p = double(mid) / d; if (Check(p)) r = mid; else l = mid + 1; } printf ("%.6f\n", double(l) / d); return 0; }

【数学|【Contra】矩阵乘法优化 dp】