Doraemon plays Tetris

 avatar
unknown
c_cpp
3 years ago
3.0 kB
7
Indexable
//Doraemon plays Tetris 

#include <stdio.h>
#define N 21

int t, n, w, arr[N], dp[N][N][N][N][N][N], win = 0;
int max(int a, int b){
    if(a > b) return a;
    else return b;
}
int solve(int ti, int a, int b, int c, int d, int e){
    int val = ti, tmp;
    if(dp[ti][a][b][c][d][e] != 0) return dp[ti][a][b][c][d][e];
    if(ti >= n){
        win = 1;
        return;
    }
    if(arr[ti] == 1){
        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));

        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));
    }
    else if(arr[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(arr[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,b),c-1);
        if(tmp+2 <= w) val = max(val, solve(ti+1, tmp+1, tmp+2, tmp+2, d, e));
        tmp = max(max(b,c),d-1);
        if(tmp+2 <= w) val = max(val, solve(ti+1, a, tmp+1, tmp+2, tmp+2, e));
        tmp = max(max(c,d),e-1);
        if(tmp+2 <= w) val = max(val, solve(ti+1, a, b, tmp+1, tmp+2, tmp+2));

        tmp = max(a-1, b);
        if(tmp+3 <= w) val = max(val, solve(ti+1, tmp+3, tmp+2, c, d, e));
        tmp = max(b-1, c);
        if(tmp+3 <= w) val = max(val, solve(ti+1, a, tmp+3, tmp+2, d, e));
        tmp = max(c-1, d);
        if(tmp+3 <= w) val = max(val, solve(ti+1, a, b, tmp+3, tmp+2, e));
        tmp = max(d-1, e);
        if(tmp+3 <= w) val = max(val, solve(ti+1, a, b, c, tmp+3, tmp+2));
    }
    return dp[ti][a][b][c][d][e] = val;
}

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