ZOJ Problem Set - 2297 Survival 【状压dp】

快来打我* 2022-08-13 00:51 5阅读 0赞

题目：[ZOJ Problem Set - 2297 Survival ][ZOJ Problem Set - 2297 Survival]

题意：给出一些怪，有两个值，打他花费的血和可以增加的血，然后有一个boss，必须把小怪所有都打死之后才能打boss，血量小于0会死，也不能大于100.

分析：定义状态：dp【st】，表示在 st 状态下的血量。

然后转移：**dp【st】 = max （dp【st】，dp【st&~(1<<i )】+p\[i\].first - p\[i\].second）;**

**注意初始化的时候必须在开始初始化，否则容易出错。**

#include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const long long N = 22;
    const int inf = 0x3f3f3f3f;
    int dp[1<<N];
    pair<int,int> p[N];
    int main()
    {
        int n,boss;
        while(~scanf("%d",&n) && n)
        {
            n--;
            for(int i=0;i<n;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                p[i]=make_pair(x,y);
            }
            scanf("%d",&boss);
            memset(dp,0,sizeof(dp));
            int ans = 0;
            dp[0]=100;
            for(int st=1;st<(1<<n);st++)
            {
                dp[st]=-inf;  //必须在这里初始化
                for(int j=0;j<n;j++)
                    if(st&(1<<j)&&dp[st&~(1<<j)]>=p[j].first)
                    {
                        dp[st]=max(dp[st],dp[st&~(1<<j)]-p[j].first+p[j].second);
                        if(dp[st]>100)
                            dp[st]=100;
                    }
            }
            if(dp[(1<<n)-1]>=boss)
                puts("clear!!!");
            else
                puts("try again");
        }
        return 0;
    }

[ZOJ Problem Set - 2297 Survival]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1297