1006번: 습격자 초라기

https://www.acmicpc.net/problem/1006

#include<cstdio>
#include<algorithm>
using namespace std;
int n, w, t, a[10001][2], dp[10001][3], r;
void f(int s) {
    if (s & 1) a[0][0] = a[n][0], a[n][0] = 1e9;
    if (s & 2) a[0][1] = a[n][1], a[n][1] = 1e9;
    for (int i = 0; i <= n; i++) {
        dp[i][0] = dp[i][1] = 1e9;
        if (a[i][0] <= w) dp[i][0] = (i ? dp[i - 1][2] : 0) + (a[i][0]>0);
        if (a[i][1] <= w) dp[i][1] = (i ? dp[i - 1][2] : 0) + (a[i][1]>0);
        if (i&&a[i][0] + a[i - 1][0] <= w) dp[i][0] = min(dp[i][0], dp[i - 1][1] + 1);
        if (i&&a[i][1] + a[i - 1][1] <= w) dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1);
        dp[i][2] = min(dp[i][0] + (a[i][1] > 0), dp[i][1] + (a[i][0] > 0));
        if (a[i][0] + a[i][1] <= w) dp[i][2] = min(dp[i][2], i ? dp[i - 1][2] + 1 : 1);
        if (i&&a[i][0] + a[i - 1][0] <= w&&a[i][1] + a[i - 1][1] <= w) dp[i][2] = min(dp[i][2], i>1 ? dp[i - 2][2] + 2 : 2);
    }
    if (s & 1) a[n][0] = a[0][0], a[0][0] = 0;
    if (s & 2) a[n][1] = a[0][1], a[0][1] = 0;
    if (s == 3) r = min(r, dp[n - 1][2]);
    if (s == 0) r = min(r, dp[n][2]);
    if (s == 1) r = min(r, dp[n][1]);
    if (s == 2) r = min(r, dp[n][0]);
}
int main() {
    for (scanf("%d", &t); t--;) {
        r = 1e9;
        scanf("%d%d", &n, &w);
        for (int i = 0; i<2; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[j][i]);
        for (int i = 0; i<4; i++) f(i);
        printf("%d\n", r);
    }
    return 0;
}