首页 > 代码库 > 6D-动态规划
6D-动态规划
n个怪物站一排让法师的火球攻击,攻击力最主怪造成a伤害,对附近的怪造成b伤害,若怪的血量低于0则死亡,求最少攻击次数并输出每次攻击的目标(不能攻击2边的怪物
#include <vector>#include <list>#include <map>#include <set>#include <queue>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <cstring>using namespace std;#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)typedef long long ll;typedef long double ld;int n, b, a;int h[20];int dp[11][20][20];int calc(int ind, int H0, int H1) { int h0 = H0, h1 = H1; if (dp[ind][H0][H1] != -1) return dp[ind][H0][H1]; int h2 = h[ind + 1]; int res = 1 << 20; int cur = 0; if (ind == n - 2) { while (h0 > 0 || h1 > 0 || h2 > 0) { cur++; h0 -= a; h1 -= b; h2 -= a; } return dp[ind][H0][H1] = cur; } while (h0 > 0) { cur++; h0 -= a; h1 -= b; h2 -= a; } for (int i = 0; i < 20; ++i) { res = min(res, cur + calc(ind + 1, max(h1, 0), max(h2, 0))); cur++; h0 -= a; h1 -= b; h2 -= a; } return dp[ind][H0][H1] = res;}string sp = "";void build(int ind, int H0, int H1) { int h0 = H0, h1 = H1; int h2 = h[ind + 1]; int res = dp[ind][H0][H1]; int cur = 0; if (ind == n - 2) { while (h0 > 0 || h1 > 0 || h2 > 0) { cout << sp << ind+1; sp = " "; cur++; h0 -= a; h1 -= b; h2 -= a; } return; } while (h0 > 0) { cout << sp << ind+1; sp = " "; cur++; h0 -= a; h1 -= b; h2 -= a; } for (int i = 0; i < 20; ++i) { if( res == cur + calc(ind + 1, max(h1, 0), max(h2, 0))) { build(ind + 1, max(h1, 0), max(h2, 0)); return; } cout << sp << ind+1; sp = " "; cur++; h0 -= a; h1 -= b; h2 -= a; }}int main() { cin >> n >> b >> a; for (int i = 0; i < n; ++i) { cin >> h[i]; h[i]++; } memset(dp, -1, sizeof dp); int res = calc(1, h[0], h[1]); cout << res << endl; build(1, h[0], h[1]); cout << endl; return 0;}
6D-动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。