Survival（ZOJ 2297状压dp)

时间：2023-03-08 15:58:22

题意：有n个怪，已知杀死第i个怪耗费的血和杀死怪恢复的血，和杀死boss耗的血，血量不能超过100，若过程中血小于0，则失败，问

是否能杀死boss（boss最后出现）.

分析:就是求杀死n个怪后剩余的最大血量 dp[i]表示杀怪情况为i（0未杀，1已杀）时剩余最大血量，注意血量上限为100，过程中血小于0，则失败即可。

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

#define N 1<<20

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  1000000007;

int dp[N],c[N],r[N],n;

int solve(){

    n=n-1;

    int cas=(1<<n);

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

        dp[i]=-INF;

   dp[0]=100;

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

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

        if(!(i&(1<<j))&&dp[i]>=c[j]){

            int t=dp[i]-c[j]+r[j];

            if(t>100)t=100;

            if(dp[i|(1<<j)]<t)

            dp[i|(1<<j)]=t;

        }

    if(dp[cas-1]>=c[n])

    printf("clear!!!\n");

    else printf("try again\n");

}

int main()

{

    while(~scanf("%d",&n)){

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

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

        scanf("%d",&c[n-1]);

        solve();

    }

return 0;

}

　　

相关文章