Doraemon plays Tetris
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...