2010-1089

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

程序解释：
struct node的定义仅仅是为了记录状态方便记忆化搜索；
move(pos, t)表示在大法师中毒还剩的持续时间pos时，t秒后大法师最多能移动多少距离；
主要函数是gao(s0, s1, pos, m, h), 就是返回当大法师位置为s0，warden位置为s1，大法师中毒还剩的持续时间pos，warden魔法值为m，大法师血量为h时，warden是否能成功杀掉大法师。

主要的判断逻辑如下：

1、先判断大法师是否已经成功跑回基地，因为题目说了是要在大法师回到基地前杀掉。

2、在大法师未回到基地的前提下，判断大法师是否已经死亡。

3、在以上的前提下，如果warden能成功地卡大法师位，那么warden以后的最优反应就是不断地放能耗血的1、2招。

4、如果未能卡位，则warden则需要尝试施放1、2、3招或者是什么招都不放，追上大法师。

5、如果以上尝试都未能返回成功，则返回无法杀死大法师。

程序如下：
{{{
#!cpp
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

int t1, p1, r1, h1;
int t2, p2, r2, h2, T;
int p3, r3;
int v0, v1;

struct node{
    int a, b, c, d, e;
    node(int a, int b, int c, int d, int e):a(a), b(b), c(c), d(d), e(e){}
};
inline bool operator <(const node &p1, const node & p2){
    if (p1.a != p2.a)
        return p1.a < p2.a;
    if (p1.b != p2.b)
        return p1.b < p2.b;
    if (p1.c != p2.c)
        return p1.c < p2.c;
    if (p1.d != p2.d)
        return p1.d < p2.d;  
        return p1.e < p2.e;  
}
map <node, int> ans;
inline int move(int pos, int t){
    int ret = 0;
    while (t--){
        if (pos-- > 0)
            ++ret;
        else
            ret += v0;
    }
    return ret;
}
bool gao(int s0, int s1, int pos, int m, int h){

    pos = max(pos, 0);

    node tmp(s0, s1, pos, m, h);
    if (ans.find(tmp) != ans.end()){
        return ans[tmp];
    }
    int &ret = ans[tmp];    

    if (s0 <= 0)
        return ret = false; 

    if (h <= 0)
        return ret = true;

    int v = pos ? 1 : v0;

    if (s0 > s1){
        if (m >= p1 && gao(s0, s1, --pos, m - p1, h - h1))
            return ret = true;
        if (m >= p2 && gao(s0, s1, --pos, m - p2, h - h2))
            return ret = true;      
    } else {
        if (m >= p1 && r1 >= abs(s1 - (s0 - move(pos, t1))) && gao(s0 - move(pos, t1), s1, pos - t1, m - p1, h - h1))
            return ret = true;
        if (m >= p2 && r2 >= abs(s1 - (s0 - move(pos, t2))) && gao(s0 - move(pos, t2), s1, T, m - p2, h - h2))
            return ret = true;
        if (m >= p3 && gao(s0 - v, max(s1 - r3, s0 - v - 1), --pos, m - p3, h))
            return ret = true;
        if (gao(s0 - v, max(s1 - v1, s0 - v), --pos, m, h))
            return ret = true;
    }   
    return false;
}

int main(){
    int s0, s1, m0, h0;
    scanf("%*d");
    while (scanf("%d%d%d%d%d%d", &s0, &s1, &v0, &v1, &m0, &h0) != EOF){

        scanf("%d%d%d%d", &t1, &p1, &r1, &h1);
        scanf("%d%d%d%d%d", &t2, &p2, &r2, &h2, &T);
        scanf("%d%d", &p3, &r3);

        ans.clear();
        printf("%s\n", gao(s0, s1, 0, m0, h0) ? "yes" : "no");
    }   
    return 0;
}
}}}

程序解释：

struct node的定义仅仅是为了记录状态方便记忆化搜索；

move(pos, t)表示在大法师中毒还剩的持续时间pos时，t秒后大法师最多能移动多少距离；

主要函数是gao(s0, s1, pos, m, h), 就是返回当大法师位置为s0，warden位置为s1，大法师中毒还剩的持续时间pos，warden魔法值为m，大法师血量为h时，warden是否能成功杀掉大法师。

主要的判断逻辑如下：

1、先判断大法师是否已经成功跑回基地，因为题目说了是要在大法师回到基地前杀掉。

2、在大法师未回到基地的前提下，判断大法师是否已经死亡。

3、在以上的前提下，如果warden能成功地卡大法师位，那么warden以后的最优反应就是不断地放能耗血的1、2招。

4、如果未能卡位，则warden则需要尝试施放1、2、3招或者是什么招都不放，追上大法师。

5、如果以上尝试都未能返回成功，则返回无法杀死大法师。

程序如下：

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
int t1, p1, r1, h1;
int t2, p2, r2, h2, T;
int p3, r3;
int v0, v1;
struct node{
    int a, b, c, d, e;
    node(int a, int b, int c, int d, int e):a(a), b(b), c(c), d(d), e(e){}
};
inline bool operator <(const node &p1, const node & p2){
    if (p1.a != p2.a)
        return p1.a < p2.a;
    if (p1.b != p2.b)
        return p1.b < p2.b;
    if (p1.c != p2.c)
        return p1.c < p2.c;
    if (p1.d != p2.d)
        return p1.d < p2.d;  
        return p1.e < p2.e;  
}
map <node, int> ans;
inline int move(int pos, int t){
    int ret = 0;
    while (t--){
        if (pos-- > 0)
            ++ret;
        else
            ret += v0;
    }
    return ret;
}
bool gao(int s0, int s1, int pos, int m, int h){
    pos = max(pos, 0);
    node tmp(s0, s1, pos, m, h);
    if (ans.find(tmp) != ans.end()){
        return ans[tmp];
    }
    int &ret = ans[tmp];    
    if (s0 <= 0)
        return ret = false; 
    if (h <= 0)
        return ret = true;
    int v = pos ? 1 : v0;
    if (s0 > s1){
        if (m >= p1 && gao(s0, s1, --pos, m - p1, h - h1))
            return ret = true;
        if (m >= p2 && gao(s0, s1, --pos, m - p2, h - h2))
            return ret = true;      
    } else {
        if (m >= p1 && r1 >= abs(s1 - (s0 - move(pos, t1))) && gao(s0 - move(pos, t1), s1, pos - t1, m - p1, h - h1))
            return ret = true;
        if (m >= p2 && r2 >= abs(s1 - (s0 - move(pos, t2))) && gao(s0 - move(pos, t2), s1, T, m - p2, h - h2))
            return ret = true;
        if (m >= p3 && gao(s0 - v, max(s1 - r3, s0 - v - 1), --pos, m - p3, h))
            return ret = true;
        if (gao(s0 - v, max(s1 - v1, s0 - v), --pos, m, h))
            return ret = true;
    }   
    return false;
}
int main(){
    int s0, s1, m0, h0;
    scanf("%*d");
    while (scanf("%d%d%d%d%d%d", &s0, &s1, &v0, &v1, &m0, &h0) != EOF){
        scanf("%d%d%d%d", &t1, &p1, &r1, &h1);
        scanf("%d%d%d%d%d", &t2, &p2, &r2, &h2, &T);
        scanf("%d%d", &p3, &r3);
        ans.clear();
        printf("%s\n", gao(s0, s1, 0, m0, h0) ? "yes" : "no");
    }   
    return 0;
}