首页 > 代码库 > 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-动态规划