Lightoj1037【状压DP】

题意：

给出n个怪的生命值，然后n个怪手里有一把枪，给出n*n的矩阵代表第i个怪对第j个怪的伤害值；

现在让你去干掉n个怪，只能平A使怪扣一滴血，干掉目标后，

可以把这个目标的武器拿进口袋然后用这个武器打别的怪

参考：大牛博客

思路：

明明也直到了状压，然后每次对于一个状态；

枚举最后被干掉的怪物，那么对于dp[i] = min(dp[i] , dp[i-(1<<j)] + 先前那个状态对这个 j 怪物的最小枪数 )；

所以还要预处理每个状态对每个怪物的最小枪数；

#include <cstdio>

#include <stack>

#include <iostream>

#include <string.h>

#include <algorithm>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const int N=1<<15;

int dp[N];

int minnum[N][20];

int mp[20][20];

char s[20];

int ww[20];

int solve(int w,int k)

{

    if(!k) return INF;

    return (w+k-1)/k;

}

int main()

{

    int n;

    int T;

    int cas=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(int i=0;i<n;i++)

            scanf("%d",&ww[i]);

        for(int i=0;i<n;i++)

        {

            scanf("%s",s);

            for(int j=0;j<n;j++)

                mp[i][j]=s[j]-'0';

        }

        for(int i=0;i<(1<<n);i++)

            for(int j=0;j<n;j++)

                minnum[i][j]=ww[j];

        for(int i=1;i<(1<<n);i++)

        {

            for(int j=0;j<n;j++)        //对于每个人求一个最小数量；

            {

                if(i&(1<<j))

                {

                    int s=i^(1<<j);     //去掉j怪物被杀死的状态；

                    for(int k=0;k<n;k++)

                    {

                        if(s&(1<<k))    //该状态下如果k怪物已经被杀死了；

                            minnum[s][j]=min(solve(ww[j],mp[k][j]),minnum[s][j]);

                    }

                }

            }

        }

        dp[0]=0;//初始化

        for(int i=1;i<=(1<<n);i++)  //从第二个怪物开始；

        {

            dp[i]=INF;

            for(int j=0;j<n;j++)

            {

                if(i&(1<<j))

                {

                    int s=i^(1<<j);

                    dp[i]=min(dp[s]+minnum[s][j],dp[i]);

                }

            }

        }

        printf("Case %d: %d\n",cas++,dp[(1<<n)-1]);

    }

    return 0;

}

巴特西

Lightoj1037【状压DP】

最新文章

热门文章