[每周一dp]Independent Attacking Zon

lightoj题目地址

题目意思是说有R，B两种军队，其中B对将军是绝对忠心的，R的说不好，所以要指挥这个军队进攻城市，需要每三个一组，组成一个三角形，然后这些三角形没有overlap，因为R的说不好，所以一个三角形里面最多就一个R。问有多少种组合方式。

典型的区间DP，我们用f[L][R]表示L,R之间有多少总组合，
那么狠明显，我们从中间选3个点i,j,k，如果i,j,k能构成三角形（最多一个R），那么方案数是,

f[L][i-1] * f[i + 1][j - 1] * f[j + 1][k - 1] * f[k + 1][R]

因为i,j,k三个点把区间分成了四个，所以总方案数就是这四个区间的组合啦，不过复杂度似乎有点高，我们可以优化一下。我们用i,j,k来分割的时候其实和用l,加上另外两个点分割是一样的效果，l早晚会被算进去，所以我们就只需要枚举两个点了。

f[L][R] = sum{f[L+1][i-1]*f[i+1][j-1]*f[j+1][R]

#include <cstdio>
#include <cstring>

const int maxn = 71;
char str[maxn];
long long f[maxn][maxn];
long long dfs(int l, int r) {
    if (l > r) return 1;
    if (f[l][r] != -1) return f[l][r];
    if ((r - l + 1) % 3) return 0;
    
    f[l][r] = 0;
    for (int i = l + 1; i <= r; i++) {
        for (int j = i + 1; j <= r; j++) {
            long long tmp = 1;
            int red = (str[l] == 'R') + (str[i] == 'R') + (str[j] == 'R');
            if (red > 1) continue;
            tmp *= dfs(l + 1, i - 1);
            tmp *= dfs(i + 1, j - 1);
            tmp *= dfs(j + 1, r);
            f[l][r] += tmp;
        }
    }
    return f[l][r];
}

int main() {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%s", str);
        memset(f, -1, sizeof(f));
        printf("Case %d: ", cas);
        printf("%lld\n", dfs(0, strlen(str) - 1));
    }
}