URAL 1152 False Mirrors 状压+记忆化搜索

英雄每秒钟可以摧毁三个连续的阳台(大Google给出的翻译。。 。 )，剩余阳台上的怪物每秒钟会对英雄造成一个单位的伤害。为英雄受到伤害的最小值是多少。

阳台数 n <= 20，且每个阳台只有两种状态。显然是状态压缩( 昨天尚神刚刚讲的→,→ )。

算了一下最多会用九秒钟，然后计算次数大约是这样(1<<20)*9，时限2000MS，所以尽情的暴力吧。

话说写代码的时候我正在看自己的位运算的博客. . . . . .然后南壕不屑的看了我一眼走了. . . . . .我没翻题解啊

状态转移方程  dp[ t ][ sta ] = min( dp[ t+1 ][ next_sta ] + next_sta中存在的怪兽和). 

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>

#pragma comment(linker, "/STACK:1024000000");
#define LL long long int
#define ULL unsigned long long int
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 1000000009

using namespace std;

int num[25];

int Min;

int dp[10][(1<<20)+10];

int dfs(int t,int sta,int n)
{
   // cout<<"t = "<<t<<" sta = "<<sta<<endl;

    if(t > 9)
        return (1<<20);
    if(dp[t][sta] != -1)
        return dp[t][sta];

    int i,temp,dag,j;

    for(i = 0;i < n; ++i)
    {
        temp = sta;
        if((temp&(1<<i)))
        {
            temp = (temp&(~(1<<i)));

            //左2

            if(i == 0)
            {
                temp = (temp&(~(1<<(n-1))));
                temp = (temp&(~(1<<(n-2))));
                dag = dfs(t+1,temp,n);
            }
            else if(i == 1)
            {
                temp = (temp&(~(1)));
                temp = (temp&(~(1<<(n-1))));

                dag = dfs(t+1,temp,n);
            }
            else
            {
                temp = (temp&(~(1<<(i-1))));
                temp = (temp&(~(1<<(i-2))));

                dag = dfs(t+1,temp,n);
            }

            for(j = 0;j < n; ++j)
            {
                if((temp&(1<<j)))
                    dag += num[j];
            }

            if(dp[t][sta] == -1 || dp[t][sta] > dag)
            {
                dp[t][sta] = dag;
            }

            temp = sta,dag = 0;

            // 右2

            if(i == n-1)
            {
                temp = (temp&(~(1<<(0))));
                temp = (temp&(~(1<<(1))));
                dag = dfs(t+1,temp,n);
            }
            else if(i == n-2)
            {
                temp = (temp&(~(1)));
                temp = (temp&(~(1<<(n-1))));

                dag = dfs(t+1,temp,n);
            }
            else
            {
                temp = (temp&(~(1<<(i+1))));
                temp = (temp&(~(1<<(i+2))));

                dag = dfs(t+1,temp,n);
            }

            for(j = 0;j < n; ++j)
            {
                if((temp&(1<<j)))
                    dag += num[j];
            }

            if(dp[t][sta] == -1 || dp[t][sta] > dag)
            {
                dp[t][sta] = dag;
            }

            temp = sta,dag = 0;

            //左右各一

            if(i == 0)
            {
                temp = (temp&(~(1<<(n-1))));
                temp = (temp&(~(1<<(1))));
                dag = dfs(t+1,temp,n);
            }
            else if(i == n-1)
            {
                temp = (temp&(~(1)));
                temp = (temp&(~(1<<(n-2))));

                dag = dfs(t+1,temp,n);
            }
            else
            {
                temp = (temp&(~(1<<(i-1))));
                temp = (temp&(~(1<<(i-2))));

                dag = dfs(t+1,temp,n);
            }

            for(j = 0;j < n; ++j)
            {
                if((temp&(1<<j)))
                    dag += num[j];
            }

            if(dp[t][sta] == -1 || dp[t][sta] > dag)
            {
                dp[t][sta] = dag;
            }
        }
    }

    return dp[t][sta];
}

int main()
{
    //freopen("sadfsdaf.txt","w",stdout);
    int n,i,sum = 0;

    scanf("%d",&n);

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

    Min = INF;

    int sta = (1<<n)-1;

    for(i = 0;i < 10; ++i)
    {
        memset(dp[i],-1,sizeof(int)*(sta+3));
    }

    for(i = 0;i <= 10; ++i)
    {
        dp[i][0] = 0;
    }

    dfs(0,sta,n);

    int Min = (1<<20);

    for(i = 0;i < 10; ++i)
    {
        if(dp[i][sta] != -1 && dp[i][sta] < Min)
            Min = dp[i][sta];
    }

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

    return 0;
}

URAL 1152 False Mirrors 状压+记忆化搜索,布布扣,bubuko.com

URAL 1152 False Mirrors 状压+记忆化搜索

原文：http://blog.csdn.net/zmx354/article/details/19931735