参考于 http://blog.csdn.net/woshi250hua/article/details/7746780
题意:吕布一个人单挑N个英雄,没打一个英雄一定要有一个人死才行,求最后如何打才能剩下的血量最多。
思路:状态DP ,dp[i]为,状态i下剩余的血量,用 0 1 表示该位置是否杀死了该敌方英雄。。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int N = 21; struct node { int ati , def , hp , exp; }dp[1<<N] , enemy[N]; char name[25]; int m_ati , m_def , m_hp , in_ati , in_def , in_hp; int n; void get_dp() { int i , j; dp[0].ati = m_ati; dp[0].def = m_def; dp[0].hp = m_hp; dp[0].exp = 0; for(i = 0 ; i <(1<<n) ; i ++) { for(j = 0 ; j < n ; j ++) { if(!(i&(1<<j)) && dp[i].hp) { //printf("运行\n"); int m_to = max(1 , dp[i].ati - enemy[j].def); //我可以打掉对方的血量 int to_m = max(1 , enemy[j].ati - dp[i].def);//对方可以打掉我的血量 int m_time = (dp[i].hp+to_m-1)/to_m; //我可以撑几次 int e_time = (enemy[j].hp+m_to-1)/m_to;//对方可以撑几次 if(m_time < e_time) continue; //干不过就pass int t_exp = dp[i].exp + enemy[j].exp; int t_ati , t_def , t_hp; t_ati = dp[i].ati; t_def = dp[i].def; /* 一些状态*/ t_hp = dp[i].hp - (e_time-1)*to_m; //我掉血的次数比对方的少一次 if(t_exp >= 100) { //升级后的状态 t_exp -= 100; t_ati += in_ati; t_def += in_def; t_hp += in_hp; } //升级 if(t_hp >= dp[i|(1<<j)].hp) { //更新 dp[i|(1<<j)].ati = t_ati; dp[i|(1<<j)].def = t_def; dp[i|(1<<j)].hp = t_hp; dp[i|(1<<j)].exp = t_exp; } } } } } int main() { while(~scanf("%d%d%d%d%d%d",&m_ati,&m_def,&m_hp,&in_ati,&in_def,&in_hp)) { scanf("%d",&n); for(int i = 0 ; i < n ; i ++) scanf("%s %d %d %d %d",name,&enemy[i].ati,&enemy[i].def,&enemy[i].hp,&enemy[i].exp); for(int i = 0 ; i < (1<<n) ; i ++) dp[i].hp = 0; get_dp(); if(dp[(1<<n)-1].hp) printf("%d\n",dp[(1<<n)-1].hp); else printf("Poor LvBu,his period was gone.\n"); } }