#include <iostream>
#include <fstream>
#include <memory.h>
#include <algorithm>
using namespace std;
#define LOST 0x7fffffff
const int M = 52, T = 41;
int case_num, m, t, instruction[M], next, curr;
double ans, dp[2][M];
double lost_this_turn[2][M];
int Clamp(int x)
{
	return (x < 0 ? 0 :(x > m ? m+1 : x));
}
void Jump(int slot, int step)
{
	int jump = Clamp(slot+step);
	double temp = (0.5*dp[curr][slot]);
	if(instruction[jump] == LOST)
	{
		dp[next][jump] += temp;
		lost_this_turn[next][jump] += temp;
	}
	else
		dp[next][Clamp(jump+instruction[jump])] += temp;
}
int main()
{
	fstream fin("1644.txt");
	char c;
	fin>>case_num;
	while(case_num--)
	{
		memset(dp, 0, sizeof(dp));
		memset(instruction, 0, sizeof(instruction));
		memset(lost_this_turn, 0, sizeof(lost_this_turn));
		dp[0][0] = 1.0;
		fin>>m>>t;
		for(int i = 1; i <=m ; i++)
		{
			fin>>c;
			if(c == 'L')
				instruction[i] = LOST;
			else
			{
				if(c != '+')
					fin.putback(c);
				fin>>instruction[i];
			}
		}
		/////////////////////////
		next = 1; curr = 0;
		for(int turn = 0; turn < t; turn++)
		{
			for(int i = 0; i <= m+1; i++)//clear next
			{
				dp[next][i]= 0.0;
				lost_this_turn[next][i] = 0.0;
			}
			for(int slot = 0; slot <= m+1; slot++)
			{
				if(dp[curr][slot])
				{
					dp[next][slot] += lost_this_turn[curr][slot];
					dp[curr][slot] -= lost_this_turn[curr][slot];
					if(slot == m+1)
						dp[next][slot] += dp[curr][slot];
					else
					{
						Jump(slot, 1);
						Jump(slot, 2);
					}
				}
			}
			next = 1-next; curr = 1-curr;
		}
		next = 1-next;
		ans = dp[next][m+1];
		int test = (int)(ans*10000+0.5);
		if(test == 5000)
			printf("%s%.4f\n", "Push. ", test/10000.0f);
		else if(test > 5000)
			printf("%s%.4f\n", "Bet for. ", test/10000.0f);
		else
			printf("%s%.4f\n", "Bet against. ", test/10000.0f);
	}
	return 0;
}

• Re:大家都试试这个数据 (182) temp_ptr 2011-10-06 15:46:05
  • Re:大家都试试这个数据 (413) temp_ptr 2011-10-06 15:53:53