找找感觉准备夏令营
上来是一道DP问题,首先需要理解清楚题意。关于dp状态的定义,开始的设置过于复杂于是参考了一些解题博客做法,定义\(dp(i, j)\)为j次到达i的概率
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <deque>
using namespace std;
const int maxm= 55;
const int maxt= 45;
const int INF= 0x3f3f3f3f;
const double eps= 1e-9;
int m, t;
char op[23];
int ins[maxm];
double dv[maxm][maxt];
int Next(int x, int d)
{
x= x+d > m ? m : x+d;
if (INF== ins[x]){
return -x;
}
else{
return min(max(x+ins[x], 0), m);
}
}
int main(int argc, char const *argv[])
{
int kase= 0;
scanf("%d", &kase);
while (kase--){
double ans= 0;
scanf("%d %d", &m, &t);
for (int i= 1; i<= m; ++i){
scanf("%s", op);
if (‘L‘== op[0]){
ins[i]= INF;
}
else{
sscanf(op, "%d", ins+i);
}
}
// notice here, change m to make code simplify
ins[++m]= ins[0]= 0;
for (int i= 0; i<= m; ++i){
for (int j= 0; j<= t; ++j){
dv[i][j]= 0;
}
}
dv[0][0]= 1;
for (int j= 0; j< t; ++j){
for (int i= 0; i< m; ++i){
int p= Next(i, 1), q= Next(i, 2);
if (p< 0){
dv[-p][j+2]+= 0.5*dv[i][j];
}
else{
dv[p][j+1]+= 0.5*dv[i][j];
}
if (q< 0){
dv[-q][j+2]+= 0.5*dv[i][j];
}
else{
dv[q][j+1]+= 0.5*dv[i][j];
}
}
}
for (int j= 0; j<= t; ++j){
ans+= dv[m][j];
}
if (ans-0.5 > eps){
printf("Bet for. %.4lf\n", ans);
}
else if (0.5-ans > eps){
printf("Bet against. %.4lf\n", ans);
}
else{
printf("Push. 0.5000\n");
}
}
return 0;
}