HDU4451Dressing（計數）

HDU4451Dressing（計數）

HDU4451Dressing（計數）

題目鏈接

題目大意：給你N件衣服， M條褲子， K雙鞋子，現在有P個不合理的的搭配（衣服和褲子或者褲子和鞋子），要求不用P中不理的搭配方式來將衣服褲子鞋子三件搭配起來有多少種方案。

解題思路：本來只要給一個不合理的搭配方案的話，那麼就是用總的搭配數目減掉2.但是可能會有衣服1 褲子1 ，褲子1 鞋子1這樣的不合裡搭配，那麼衣服1 褲子1 鞋子1就多減了一次。因為這裡都是由褲子來關聯的，那麼就將每條褲子不能搭配的衣服和鞋子的數目都記錄下來，最後枚舉一邊褲子，一邊累計（N - 和這條褲子不搭的衣服數目） ? （K - 和這條褲子不搭的鞋子）

代碼：

#include 
#include 

const int maxn = 1e3 + 5;
int vis1[maxn][maxn], vis2[maxn][maxn];
int c[maxn], s[maxn];

int main () {

    int N, M, K, P;
    int a, b;
    char str1[10], str2[10];
    while (scanf ("%d%d%d", &N, &M, &K) && (N || M ||K)) {

        memset (vis1, 0, sizeof (vis1));
        memset (vis2, 0, sizeof (vis2));
        memset (c, 0, sizeof (c));
        memset (s, 0, sizeof (s));

        scanf ("%d", &P);
        for (int i = 0; i < P; i++) {
            scanf ("%s%d%s%d", str1, &a, str2, &b);
            if (str1[0] == 'c' && str2[0] == 'p') {

                if (!vis1[a][b]) {
                    vis1[a][b] = 1;
                    c[b]++;
                }
            }

            if (str1[0] == 'p' && str2[0] == 's') {
                if (!vis2[a][b]) {
                    vis2[a][b] = 1;
                    s[a]++;
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= M; i++)
            ans += (N - c[i]) * (K - s[i]);
        printf ("%d\n", ans);
    }
    return 0;
}