ZOJ Problem Set - 2297 Survival 【状压dp】

快来打我* 2022-08-13 00:51 22阅读 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

发表评论取消回复

表情：

评论列表（有 0 条评论，22人围观）

还没有评论，来说两句吧...

相关阅读

相关【状压DP】Most Powerful

[E-Most Powerful\_牛客竞赛动态规划专题班状压dp例题 (nowcoder.com)][E-Most Powerful_dp_ _nowcoder.com]

以你之姓@/ 2024年03月17日 08:58/ 0 赞/ 72 阅读

相关【状压DP】简单环

怎么办，感觉现在所谓会的算法都是云的以为自己会，然后随便出一道题就不会云玩家是吧好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好

柔情只为你懂/ 2024年03月17日 08:57/ 0 赞/ 58 阅读

相关 group 状压dp

　　应某些人要求，我把标签删掉了　　这是一道好题。　　一看$c<=16$果断状压，但是怎么压？　　一个很显然的思路是，枚举上下两层的状态，每一层的状态极限有$C（c

逃离我推掉我的手/ 2023年08月17日 16:48/ 0 赞/ 138 阅读

相关 ZOJ Problem Set - 2965

Accurately Say "CocaCola"! -------------------- Time Limit: 2 Seconds Memory Limit:

谁借莪１个温暖的怀抱￠/ 2022年08月20日 07:18/ 0 赞/ 20 阅读

相关 ZOJ Problem Set - 2563 Long Dominoes 【状压dp】

题目：[ZOJ Problem Set - 2563 Long Dominoes][] 题意：给出1\3的小矩形，求覆盖m\n的矩阵的最多的不同的方法数？

朱雀/ 2022年08月13日 00:53/ 0 赞/ 19 阅读

相关 ZOJ Problem Set - 2297 Survival 【状压dp】

题目：[ZOJ Problem Set - 2297 Survival ][ZOJ Problem Set - 2297 Survival] 题意：给出一些怪，有两

快来打我*/ 2022年08月13日 00:51/ 0 赞/ 23 阅读

相关 ZOJ Problem Set - 1005 Jugs

文章出处：http://blog.csdn.net/rongyongfeikai2/article/details/7315702 作者思路简单易懂，借鉴了~~~ Jug

短命女/ 2022年08月01日 14:00/ 0 赞/ 19 阅读

相关 HDU3182-状压dp

Hamburger Magi Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

川长思鸟来/ 2022年07月13日 14:56/ 0 赞/ 222 阅读

相关状压dp（瞎BB）

最近在写状压dp，写得不太顺利啊，抠很久才抠出来。可见如此之菜。状态压缩dp（简称状压dp）是一种非常典型的动态规划，通常使用在NP问题的小规模求解中，虽然是指数

迷南。/ 2022年06月17日 08:13/ 0 赞/ 242 阅读

相关 Problem Arrangement (状压DP)

Problem Arrangement [ZOJ - 3777 ][ZOJ - 3777] The 11th Zhejiang Provincial Collegiat

た入场券/ 2021年12月13日 01:35/ 0 赞/ 310 阅读