Untitled

 avatar
unknown
c_cpp
3 years ago
3.0 kB
9
Indexable
#include <stdio.h>
#include <string.h>

#define N 21

int t, n, w, p[N], dp[N][N][N][N][N][N];

int max(int x, int y) {
    return x > y ? x : y;
}

int solve(int ti, int a, int b, int c, int d, int e) {
    if (dp[ti][a][b][c][d][e] != -1) return dp[ti][a][b][c][d][e];
    if (ti >= n) return dp[ti][a][b][c][d][e] = n+1;
    int val = ti+1, tmp;
    if (p[ti] == 1) {

        if (a+4 <= w) val = max(val, solve(ti+1, a+4, b, c, d, e));
        if (b+4 <= w) val = max(val, solve(ti+1, a, b+4, c, d, e));
        if (c+4 <= w) val = max(val, solve(ti+1, a, b, c+4, d, e));
        if (d+4 <= w) val = max(val, solve(ti+1, a, b, c, d+4, e));
        if (e+4 <= w) val = max(val, solve(ti+1, a, b, c, d, e+4));

        tmp = max(max(a, b), max(c, d));
        if (tmp+1 <= w) val = max(val, solve(ti+1, tmp+1, tmp+1, tmp+1, tmp+1, e));
        tmp = max(max(b, c), max(d, e));
        if (tmp+1 <= w) val = max(val, solve(ti+1, a, tmp+1, tmp+1, tmp+1, tmp+1));

    } else if (p[ti] == 2) {

        tmp = max(a, b);
        if (tmp+2 <= w) val = max(val, solve(ti+1, tmp+2, tmp+2, c, d, e));
        tmp = max(b, c);
        if (tmp+2 <= w) val = max(val, solve(ti+1, a, tmp+2, tmp+2, d, e));
        tmp = max(c, d);
        if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, tmp+2, tmp+2, e));
        tmp = max(d, e);
        if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, c, tmp+2, tmp+2));

    } else if (p[ti] == 3) {

        tmp = max(max(a, b+1), c);
        if (tmp+2 <= w) val = max(val, solve(ti+1, tmp+1, tmp+2, tmp+1, d, e));
        tmp = max(max(b, c+1), d);
        if (tmp+2 <= w) val = max(val, solve(ti+1, a, tmp+1, tmp+2, tmp+1, e));
        tmp = max(max(c, d+1), e);
        if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, tmp+1, tmp+2, tmp+1));

    } else {

        tmp = max(max(a+1, b+1), c);
        if (tmp+1 <= w) val = max(val, solve(ti+1, tmp, tmp+1, tmp+1, d, e));
        tmp = max(max(b+1, c+1), d);
        if (tmp+1 <= w) val = max(val, solve(ti+1, a, tmp, tmp+1, tmp+1, e));
        tmp = max(max(c+1, d+1), e);
        if (tmp+1 <= w) val = max(val, solve(ti+1, a, b, tmp, tmp+1, tmp+1));

        tmp = max(a, b+1);
        if (tmp+2 <= w) val = max(val, solve(ti+1, tmp+2, tmp+1, c, d, e));
        tmp = max(b, c+1);
        if (tmp+2 <= w) val = max(val, solve(ti+1, a, tmp+2, tmp+1, d, e));
        tmp = max(c, d+1);
        if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, tmp+2, tmp+1, e));
        tmp = max(d, e+1);
        if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, c, tmp+2, tmp+1));

    }
    return dp[ti][a][b][c][d][e] = val;
}

int main() {
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&n,&w);
        for (int i=0; i<n; i++) scanf("%d",&p[i]);
        memset(dp, -1, sizeof(dp));
        int ans = solve(0, 0, 0, 0, 0, 0);
        if (ans == n+1) printf("Win\n");
        else printf("Lose at %d\n",ans);
    }
}
Editor is loading...