HDU 1152. False Mirrors（DFS啊 ）

题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1152

Background

Problem

Input

Output

Sample

7
3 4 2 2 1 4 1

9

题意：

一共有n个阳台，首尾相接形成一个环；

阳台里有怪物，伤害为a[i]，每次可以打掉三个阳台（打掉中间的一个左右相邻的也被打掉了），那么同时，没被打掉的那些怪物会对你造成响应a[i]的伤害。经过几次战斗，打掉所有阳台的怪物，问受到的伤害最小是多少。

代码如下：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double e = exp(1.0);
#define INF 0x3f3f3f3f
int n,sum;
int a[47];
int vis[47];
int ans;
void DFS(int num, int tt)//个数,伤害
{
    if(tt >= ans)
    {
        return ;//伤害大于总的怪兽数
    }
    if(num == 0)//怪兽已经没有了
    {
        ans = min(tt, ans);
        return ;
    }

    for(int i = 1; i <= n; i++)//围城一个圈
    {
        if(vis[i])
        {
            continue;
        }
        int t1 = i-1, t2 = i+1;
        if(t1 == 0)
        {
            t1 = n;
        }
        if(t2 == n+1)
        {
            t2 = 1;
        }
        int flag1 = 0, flag2 = 0;
        if(vis[t1])
        {
            flag1 = 1;
        }
        if(vis[t2])
        {
            flag2 = 1;
        }
        int num1 = 0, num2 = 0;
        if(!flag1)
        {
            num1 = a[t1];
            vis[t1] = 1;//死掉
        }
        if(!flag2)
        {
            num2 = a[t2];
            vis[t2] = 1;//死掉
        }
        int tt_num = a[i]+num1+num2;
        num-=tt_num;
        vis[i] = 1;
        tt+=num;
        DFS(num, tt);
        tt-=num;
        num+=tt_num;
        vis[i] = 0;
        if(!flag1)
        {
            vis[t1] = 0;
        }
        if(!flag2)
        {
            vis[t2] = 0;
        }
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(vis, 0,sizeof(vis));
        memset(a, 0,sizeof(a));
        ans = INF;
        int tol = 0;
        a[0] = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            tol += a[i];
        }
        DFS(tol, 0);
        printf("%d\n",ans);
    }
    return 0;
}

HDU 1152. False Mirrors（DFS啊 ）

原文：http://blog.csdn.net/u012860063/article/details/44540829