首页 > 代码库 > ZOJ Problem Set - 2297 Survival 【状压dp】
ZOJ Problem Set - 2297 Survival 【状压dp】
题目: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 【状压dp】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。