# Doraemon plays Tetris

unknown
c_cpp
2 years ago
3.0 kB
3
Indexable
Never
```//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;
}
}
```