本文主要是介绍hdu 2891 addHP 二分+dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
数据水。。。。！！！
二分+dp
由于时间最多1000，所以有用的加血技能最多1000个。而实际测试发现，远远没有1000个。
二分一个最低血量mid， dp[i] 表示 满足血量始终不低于mid，第i秒能达到的最高血量
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;
void fre(){freopen("t.txt","r",stdin);}
#define ls o<<1
#define rs o<<1|1
#define MS(x,y) memset(x,y,sizeof(x))
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
const int INF = 0x3f3f3f3f;
const int dir[4][2] = {1,0,0,1,-1,0,0,-1};
const int MAXN = 5010;
const int MAXM = MAXN*16;
const double pi = acos(-1.0);char IN;
int NEG;
inline void Int(int &x){NEG = 0;while(!isdigit(IN=getchar()))if(IN=='-')NEG = 1;x = IN-'0';while(isdigit(IN=getchar()))x = x*10+IN-'0';if(NEG)x = -x;
}int n,m,hp,dp[10010],add[1010],sub[10010],nxt[1010];
void solve()
{int time,tem;for(int i = 1; i <= n; ++i){Int(sub[i]);add[i] = 0;sub[i] += sub[i-1];}while(m--){Int(time);Int(tem);if(tem > add[time]) add[time] = tem;}nxt[1000] = 10000;for(int i = 999; i >= 0; --i)if(add[i+1]) nxt[i] = i+1;else nxt[i] = nxt[i+1];int l = 0,r = hp,ans = 0;while(l <= r){int mid = (l+r)>>1;for(int i = 1; i <= n; ++i) dp[i] = 0;dp[0] = hp;for(int i = 0; i < n; ++i){for(int j = 1; i+j <= n; j = nxt[j]){if(dp[i] - sub[i+j] + sub[i] >= mid && dp[i]+add[j]-sub[i+j]+sub[i] > dp[i+j]){dp[i+j] = dp[i]+add[j]-sub[i+j]+sub[i];if(dp[i+j] > hp) dp[i+j] = hp;}}}if(dp[n] >= mid) ans = mid,l = mid+1;else r = mid-1;}if(ans == 0) printf("Die\n");else printf("%d\n",ans);
}
int main()
{//fre();while(~scanf("%d%d%d",&n,&m,&hp))solve();return 0;
}
这篇关于hdu 2891 addHP 二分+dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
