URAL 1152. False Mirrors

Author: 2015-10-31

ACM

, , ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1152

1152. False Mirrors

Time limit: 2.0 second
Memory limit: 64 MB

Background

We wandered in the labyrinth for twenty minutes before finally entering the large hall. The walls were covered by mirrors here as well. Under the ceiling hung small balconies where monsters stood. I had never seen this kind before. They had big bulging eyes, long hands firmly holding riffles and scaly, human-like bodies. The guards fired at me from the balconies, I shot back using my BFG-9000. The shot shattered three mirrors filling the room with silvery smoke. Bullets drummed against my body-armor knocking me down to the floor. Falling down I let go a shot, and got up as fast as I fell down by rotating on my back, like I did in my youth while break dancing, all this while shooting three more times. Three mirrors, three mirrors, three mirrors…
Sergey Lukjanenko, “The Labyrinth of Reflections”

Problem

BFG-9000 destroys three adjacent balconies per one shoot. (N-th balcony is adjacent to the first one). After the shoot the survival monsters inflict damage to Leonid (main hero of the novel) — one unit per monster. Further follows new shoot and so on until all monsters will perish. It is required to define the minimum amount of damage, which can take Leonid.

Input

The first line contains integer N, аmount of balconies, on which monsters have taken a circular defense. 3 ≤ N ≤ 20. The second line contains N integers, amount of monsters on each balcony (not less than 1 and no more than 100 on each).

Output

Output minimum amount of damage.

Sample

input output 
7
3 4 2 2 1 4 1

9
Problem Author: Eugene Bryzgalov
Problem Source: Ural Collegiate Programming Contest, April 2001, Perm, English Round

2. 思路

N个台子首尾相连构成一个环，每个台子上有一些怪，使用BFG-9000射击一个台子，可以摧毁该台子和其左右相邻的台子。每回合都遵循“射击台子->剩余台子上的所有怪物攻击”这样的顺序，每只怪每回合造成1点伤害，求摧毁所有台子所受到的最小伤害。

最多只有20个台子，DFS暴力求解。也可以DP。

3. 代码

#include <cstdio>

#define MAX_N 20
#define MAX_DAMAGE 20000

void solvePE8d_FalseMirrors();
int input(int balconies[]);
void dfs(int damage);
int getDamage();
void setDestoryed(int id, bool isDestoryed);
int getCode();

int main() {
    // freopen("test.txt", "r", stdin);
    solvePE8d_FalseMirrors();
    return 0;
}


bool destoryed[MAX_N], visited[1048576];
int balconies[MAX_N], n, minDamage = MAX_DAMAGE;
void solvePE8d_FalseMirrors() {
    n = input(balconies);

    for (int i = 0; i < n; ++i) {
        setDestoryed(i, true);
        int damage = getDamage();
        int code = getCode();
        if (visited[code] == false) {
            dfs(damage);
            visited[code] = true;
        }
        setDestoryed(i, false);
    }

    printf("%d\n", minDamage);

}

void printDes() {
    for (int i = 0; i < n; ++i) {
        if (destoryed[i]) {
            printf("1 ");
        }
        else {
            printf("0 ");
        }
    }
    printf("\n");

}

void dfs(int damage) {
    if (damage > minDamage) {
        return;
    }
    bool hasMore = false, needRecover[2] = { false, false };
    for (int i = 0; i < n; ++i) {
        if (!destoryed[i]) {
            needRecover[0] = false;
            needRecover[1] = false;
            hasMore = true;
            destoryed[i] = true;
            int nextId = (i + 1) % n;
            if (destoryed[nextId] == false) {
                destoryed[nextId] = true;
                needRecover[1] = true;
            }
            int lastId = (i - 1) < 0 ? (n - 1) : (i - 1);
            if (destoryed[lastId] == false) {
                destoryed[lastId] = true;
                needRecover[0] = true;
            }

            int currDamage = damage + getDamage();
            int code = getCode();
            if (visited[code] == false) {
                visited[code] = true;
                dfs(currDamage);
                visited[code] = false;
            }

            destoryed[i] = false;
            if (needRecover[0]) {
                destoryed[lastId] = false;
            }
            if (needRecover[1]) {
                destoryed[nextId] = false;
            }

        }
    }

    if (!hasMore) {
        minDamage = minDamage < damage ? minDamage : damage;
    }

}

int getDamage() {
    int damage = 0;
    for (int i = 0; i < n; ++i) {
        if (!destoryed[i]) {
            damage += balconies[i];
        }
    }
    return damage;
}
int getCode() {
    int code = 0;
    for (int i = 0; i < n; ++i) {
        if (destoryed[i]) {
            code += 1 << i;
        }
    }
    return code;
}
void setDestoryed(int id, bool isDestoryed) {
    destoryed[id] = isDestoryed;
    destoryed[(id + 1) % n] = isDestoryed;
    destoryed[(id - 1) < 0 ? (n - 1) : (id - 1)] = isDestoryed;
}



int input(int balconies[]) {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        scanf("%d", &balconies[i]);
    }

    return n;
}