首页 > ACM题库 > HDU-杭电 > HDU 4044-GeoDefense-动态规划-[解题报告]HOJ
2015
04-16

HDU 4044-GeoDefense-动态规划-[解题报告]HOJ

GeoDefense

问题描述 :

Tower defense is a kind of real-time strategy computer games. The goal of tower defense games is to try to stop enemies from reaching your bases by building towers which shoot at them as they pass.
FXTZ II

The choice and positioning of the towers is the essential strategy of the game. Many games, such as Flash Element Tower Defense, feature enemies that run through a "maze", which allows the player to strategically place towers for optimal effectiveness. However, some versions of the genre force the user to create the maze out of their own towers, such as Desktop Tower Defense. Some versions are a hybrid of these two types, with preset paths that can be modified to some extent by tower placement, or towers that can be modified by path placement.

geoDefense is a Thinking Man’s Action Tower Defense. It has become one of "PC World’s 10 iPhone Games You CANNOT Live Without". Using exciting vectorized graphics, this highly kinetic game brings a whole new dimension to the defense genre. Devastate creeps with blasters, lasers and missiles and watch their energy debris swirl through the gravity wells of your vortex towers.

There is a geoDefense maze of n points numbered from 1 and connected by passageways. There are at least two dead ends among these n points, and there is always one and only one path between any pair of points. Point 1 is a dead end, and it’s the base of enemies, and all the other dead ends are your bases.

To prevent the enemy reaching your bases, you have to construct towers to attack the enemy. You can build tower on any point and you can only build one tower on one point. A tower can only shot the enemy when it passes the tower. You are given ki choices to build tower on point i, and each choice is given in the format of (price, power) which means that you can build a tower with attack power value equals power in the cost of price. You can also build nothing on a point so it will not cost your money. A tower will reduce the enemy’s HP by its attack power. When the HP is less or equal to zero, the enemy dies immediately.

The base of enemies will release only one enemy. It moves very fast that you cannot do anything such as building towers while it is running. It runs all the way until it dies or reaches one of your bases. However, you cannot predict the route it will go through. To win the game, you must kill the enemy before it reaches your bases. You have to strategically place towers for optimal effectiveness so that the fortifications are steady enough to protect the bold and powerful enemy with high HP. You are troubling your head on figuring out the highest HP of the enemy you are able to kill on the way certainly. You have money m when the game begins.
Please note that the towers build in the enemy’s base or your bases are all effective and if the enemy is shot to death in your bases, you still win.

输入:

The input consists of several test cases. The first line is an integer T (1 <= T <= 20), which shows the number of the cases.
For each test case, the first line contains only one integer n (2 <= n <= 1000) meaning the number of points.
The following n-1 lines describe the passageways. Each line contains two integers u and v, which are the endpoints of a passageway.
The following line contains only one integer m (1 <= m <= 200) meaning the amount of your money when the game begins.
Then n lines follow. The ith line describes the construction choices of the ith point. It starts with an integer ki (0 <= ki <= 50) and ki is followed by ki pairs of integers separated by spaces. The jth pair is (pricei,j, poweri,j), 0 <= pricei,j <= 200, 0 <= poweri,j <= 50000. ki being zero means that you can’t build a tower on the ith point.

输出:

The input consists of several test cases. The first line is an integer T (1 <= T <= 20), which shows the number of the cases.
For each test case, the first line contains only one integer n (2 <= n <= 1000) meaning the number of points.
The following n-1 lines describe the passageways. Each line contains two integers u and v, which are the endpoints of a passageway.
The following line contains only one integer m (1 <= m <= 200) meaning the amount of your money when the game begins.
Then n lines follow. The ith line describes the construction choices of the ith point. It starts with an integer ki (0 <= ki <= 50) and ki is followed by ki pairs of integers separated by spaces. The jth pair is (pricei,j, poweri,j), 0 <= pricei,j <= 200, 0 <= poweri,j <= 50000. ki being zero means that you can’t build a tower on the ith point.

样例输入:

2
2
1 2
30
3 10 20 20 40 30 50
3 10 30 20 40 30 45
4
2 1
3 1
1 4
60
3 10 20 20 40 30 50
3 10 30 20 40 30 45
3 10 30 20 40 30 35
3 10 30 20 40 30 35

样例输出:

70
80

//该题链接http://acm.hdu.edu.cn/showproblem.php?pid=4044
/* 报告人:SpringWater(GHQ)

  //此题大意:一个以1为根节点的树,每个节点可以有修防御系统,每个节点的
  防御系统(具有不同的价格和防御力)有chioce种可能的选择,敌人的基地为根节点,我方的基地为所有的叶
  子节点,敌人可以随机发射一个攻击(具有一定的攻击力指数),当遇到你在某节点上修的防御拦截系统时,
  它的攻击力会减去你该点的防御力,当它到达你的基地后经历了你所有的防御系统都还有剩余攻击力(即攻击
  力为正值)的话,那你就输了!否则你就防御成功,题目要求,加入给你一定的money,问你能用这些钱所能
  修建出最大的稳定防御力是多少(即敌人只要超过这个值就有可能将你打败);

  解题思路:根据题意可判定是一个树形DP问题;即需算出每个点i,在给予j的钱,所能修建出的出的最大的稳定防御力;
  即dp[i][j];所以再用最小背包解决即可;但此题的难点是,对于i来说他要求出的是在钱为j的前提下,最大攻击力,而对于孩子
  来说,是求最大的最小防御力(听起来很别扭是吧!其实关键处理也在这里了!),这里的最小是指:当按照某种方式分配钱,来
  修防御系统时,最薄弱(最小)的防御孩子是多少;而最大是指:在所有的方式中求得最大的那个最薄弱防御值,这就可以求得
  不考虑i的情况下的dp[i][j]值,之后再在此基础上讨论i选择哪种拦截系统,这就是一个简单的背包dp问题了,故该题用了两次
  dp来将问题简化是我觉得我最精华的部分了(嘻嘻!),动态方程如下:

  第一次dp:在只讨论i的孩子dp[i][j]=max{(power<dp[i][j-price])?power:dp[i][j-price]}  (涉及到既要利用dp[i][j],
  又要初始化为0来求最大值,所以我就私自多用了一个temp[210]来中介)

  第二次dp:只讨论i: dp[i][j]=max{dp[i][j],dp[i][j-price]+power}

  回头感悟:虽然我这代码排在static的第二名,但是还是有几点不足,比如 (1)第二次dp就没有必要多用一个temp来
  中转直接从最大money……0即可解决(2)在处理第一dp的时候,我花的时间太长,可能 是因为第一次独立编这种树
  形dp吧,我想在今后的不断练习中,思维就更加成熟,编码就更加熟练!练习!练习!还是练习!噢!别忘了总结!嘻嘻!

*/

#include<stdio.h>
#include<string.h>
struct tree{
    int k[60][2];
    int son;
}node[1010];//用于保存各节点的信息
struct see
{
    int point;
    int next;
}seek[2010];//用于索引个点的孩子
int count[1010];//记录每个节点有多少种choice
int seek_num;
int money;
int dp[1010][210],temp[210];
int add_son(int sta,int end)//建立索引表
{
    seek_num++;    seek[seek_num].point=end;      seek[seek_num].next=node[sta].son;     node[sta].son=seek_num;
    seek_num++; seek[seek_num].point=sta;     seek[seek_num].next=node[end].son;  node[end].son=seek_num;
    return 0;
};
int fun(int fa,int ffa)//  dp加递归
{
    int i,j,k,min;
    int price,power;
    int first,ii;
    for(i=node[fa].son;i!=0;i=seek[i].next)//索引fa的所有孩子再进行递归
    {
        if(seek[i].point!=ffa)//防止死锁
            fun(seek[i].point,fa);//递归
    }
    first=1;
    for(i=node[fa].son;i!=0;i=seek[i].next)//索引fa的所有孩子i,分别在i以前的兄弟都已经进行dp的基础上进行dp
    {
        if(seek[i].point!=ffa)
        {
            if(first)//当是i第一个孩子时dp[fa][ii]的值为dp[i][ii];
            {
                first=0;
                for(ii=0;ii<=money;ii++)
                    dp[fa][ii]=dp[seek[i].point][ii];
            }
            else
            {
            memset(temp,0,sizeof(temp));
            for(j=money;j>=0;j--) //注意这里没有严格要求一定是从money……0,因为我用了一个temp
            {
                for(k=0;k<=j;k++)//进行dp[i][j]=max{(power<dp[i][j-price])?power:dp[i][j-price]}
                {
                    min=(dp[seek[i].point][k]<dp[fa][j-k])?dp[seek[i].point][k]:dp[fa][j-k];
                    if(min>temp[j])
                        temp[j]=min;
                }
            }
            for(j=0;j<=money;j++)
                dp[fa][j]=temp[j];
            }
        }
    }
    memset(temp,0,sizeof(temp));//这是一大败笔,但是考虑到这也是我的一个成长历程,纪念一下,就没去改了,
                                //有兴趣的你可以试试去掉它!(提示:内外循环交换)

    for(i=0;i<=count[fa];i++)//此只讨论i的各种选择
    {
        if(!i)
            price=power=0;//当fa点一个防御系统都不修建的情况!
        else
            price=node[fa].k[i][0],power=node[fa].k[i][1];
        for(j=money;j>=0;j--)//进行dp[i][j]=max{dp[i][j],dp[i][j-price]+power}
        {
            if(j>=price)
            {
                if(temp[j]<power+dp[fa][j-price])
                    temp[j]=power+dp[fa][j-price];
            }
            else
                break;
        }
    }
    for(j=0;j<=money;j++)
        dp[fa][j]=temp[j];
    return 0;
}

int main()
{
    int T,i,j,n;
    int v,u,choice;
//    freopen("input.txt","r",stdin);
    scanf("%d",&T);//测试数据
    while(T--)
    {
        scanf("%d",&n);//节点数
        for(i=1;i<=n;i++)//初始化,为索引做准备
            node[i].son=0;
        for(i=0;i<2010;i++)//初始化,为索引做准备
            seek[i].next=0;
        seek_num=0;//初始化,为索引做准备
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&v,&u);
            add_son(v,u);//分别为v,u增加儿子
        }
        scanf("%d",&money);//总的钱
        for(i=1;i<=n;i++)
        {
            scanf("%d",&choice);//每个点有多少种选择
            count[i]=choice;
            for(j=1;j<=choice;j++)
                scanf("%d%d",&node[i].k[j][0],&node[i].k[j][1]);//防御系统对应的价格和防御能力值
        }
        memset(dp,0,sizeof(dp));
        fun(1,-1);//调用递归进行树形dp
        printf("%d\n",dp[1][money]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sprintfwater/article/details/7861875


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 不考虑最后将结果排序的话,快排的时间复杂度是O(N) ,而堆排的是O(N*logK),这样比较看,快排快