AOJ 0232 - Life Game

問題文 : 人生ゲーム

解法 :
dp(i, j) -> 場所iにいてj円を持っている確率, とし動的計画法を行う.
int型にキャストして表示することに注意.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef struct {
    int dx;
    int money;
} State;

using namespace std;

int main(void)
{
    State map[51];
    int mx[4];
    int x, y, z;
    int n, e, a;
    int i, j, k;
    static double dp[51][5001];
	double res;
    
    while (1){
        scanf("%d%d%d", &x, &y, &z);
        
        if (x + y + z == 0){
            break;
        }
        
        for (i = 0; i < x; i++){
            scanf("%d", &mx[i]);
        }
        for (i = 0; i <= 50; i++){
			map[i].dx = map[i].money = 0;
        }
        for (i = 0; i < z; i++){
            scanf("%d%d%d", &n, &e, &a);
            
            if (e == 1){
                map[n].dx = a;
            }
            else if (e == 2){
                map[n].money = a;
            }
            else {
                map[n].money = -a;
            }
        }
        
        for (i = 0; i <= 50; i++){
			for (j = 0; j <= 5000; j++){
				dp[i][j] = 0;
			}
        }
		dp[0][0] = 1.0;
		
        for (i = 0; i < y; i++){
			for (j = 0; j <= 5000; j++){
				int tx, tm;
				for (k = 0; k < x; k++){
					tx = min(i + mx[k], y);
					tm = max(0, map[tx].money + j);
					tx = max(0, min(tx + map[tx].dx, y));
					
					dp[tx][tm] += dp[i][j] * (1.0 / x);
				}
			}
        }
		res = 0;
		for (i = 0; i <= 5000; i++){
			res += dp[y][i] * i;
		}
		
		printf("%d\n", (int)res);
    }
    
    return (0);
}