MyException - 我的异常网
当前位置:我的异常网» 综合 » 动态规划背包有关问题-做题小总结

动态规划背包有关问题-做题小总结

www.MyException.Cn  网友分享于:2013-08-29  浏览:0次
动态规划背包问题--做题小总结

题目来源:2017“百度之星”晋级赛 1003

 

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

 

Problem description:

度度熊为了拯救可爱的公主,于是与邪恶大魔王战斗起来。

邪恶大魔王的麾下有n个怪兽,每个怪兽有a[i]的生命值,以及b[i]的防御力。

度度熊一共拥有m种攻击方式,第i种攻击方式,需要消耗k[i]的晶石,造成p[i]点伤害。

当然,如果度度熊使用第i个技能打在第j个怪兽上面的话,会使得第j个怪兽的生命值减少p[i]-b[j],当然如果伤害小于防御,那么攻击就不会奏效。

如果怪兽的生命值降为0或以下,那么怪兽就会被消灭。

当然每个技能都可以使用无限次。

请问度度熊最少携带多少晶石,就可以消灭所有的怪兽。

 

Input:

本题包含若干组测试数据。

第一行两个整数n,m,表示有n个怪兽,m种技能。

接下来n行,每行两个整数,a[i],b[i],分别表示怪兽的生命值和防御力。

再接下来m行,每行两个整数k[i]和p[i],分别表示技能的消耗晶石数目和技能的伤害值。

数据范围:

1<=n<=100000

1<=m<=1000

1<=a[i]<=1000

0<=b[i]<=10

0<=k[i]<=100000

0<=p[i]<=1000

 

Output:

对于每组测试数据,输出最小的晶石消耗数量,如果不能击败所有的怪兽,输出-1.

 

解析:

    这是一道动态规划的题目,其思想就是比较经典的背包问题的思想。首先我们考虑单独的一个怪兽i,问打败该怪兽最少的花费是多少。

对于技能序列(k,p),进行动态规划。令数组F[i][j]代表的含义为:当1到i技能可选时,打败生命值为j的怪兽所需的最小花费。

对于打败所有怪兽的花费则是打败每个怪兽的最小花费的叠加。

这里需要统计每个怪兽被打败的最小花费,当然不能对每一个怪兽都进行一次动态规划。采取的办法是预先处理出一个cnt[i][j]数组,记录对于防御值为i, 生命值为j的怪兽所需的最小花费。我们发现防御值B_j的范围比较小,0~10,这是一个切入点。我们可以枚举B,并对应每个防御值,进行动态规划。

具体的过程分为三种情况:

1)f[i][j] = min(经此攻击之后的f’[i][j]+此攻击的花费,不采用此攻击的花费),因而限制条件是经历此攻击之后的f’[i][j]是存在的:j-p[i]+B>0,当然此攻击是有效的:p[i]>B。

if(p[i] > B && (j-p[i]+B) > 0)

       f[i][j] = _min(f[i][j-p[i]+B]+k[i],f[i-1][j]);

 

2)如果该次攻击就已经消灭了怪兽,则直接将本次攻击的花费,与不采用此攻击的花费进行对比。

else if(p[i] > B && (j-p[i]+B) <= 0)

       f[i][j] = _min(k[i],f[i-1][j]);

 

3)如果该攻击是无效的,则不采取该攻击,f[i][j] = f[i-1][j].

else if(p[i] <= B)

       f[i][j] =  f[i-1][j];

  

   整个算法的思路就是这样。F[i][j]这个二维数组对于不同的B可以重复利用,当B更新时,对F数组进行初始化即可。每次动态规划完毕,对cnt[][]进行赋值。

 

Code:

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

#include <cstring>

#include <queue>

#include <ctime>

#include <set>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair<int,int> pii;

const ll INF = 10e16;

const int maxN = 100010;

const int maxM = 1010;

const int maxK = 16;

int a[maxN];

int b[maxN];

int k[maxN];

int p[maxN];

 

ll f[maxM][maxM];

ll cnt[12][maxM];

ll _min(ll a,ll b)

{

    if(a>b)

        return b;

    else

        return a;

}

void _clr(int m)   //清空

{

    for(int i=0;i<=m;i++)

        for(int j=0;j<maxM;j++)

        {

            if(i==0 && j==0)

                f[i][j] = 0;

            else

                f[i][j] = INF;

        }

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m) !=EOF)

    {

        for(int i=1;i<=n;i++)

        {

            scanf("%d%d",&a[i],&b[i]);   

        }           

        int maxp = 0;                    //找到最大攻击力

        for(int i=1;i<=m;i++)

        {

            scanf("%d%d",&k[i],&p[i]);

            maxp = max(maxp,p[i]);

        }

        for(int B=0;B<=10;B++)

        {

            _clr(m);

            for(int i=1;i<=m;i++)

            {

                for(int j=1;j<maxM;j++)

                {

                    if(p[i] > B && (j-p[i]+B) > 0)

                        f[i][j] = _min(f[i][j-p[i]+B]+k[i],f[i-1][j]);

                    else if(p[i] > B && (j-p[i]+B) <= 0)

                        f[i][j] = _min(k[i],f[i-1][j]);

                    else if(p[i] <= B)

                        f[i][j] =  f[i-1][j];

                }

            }

            for(int j=1;j<maxM;j++)

            {

                cnt[B][j] = f[m][j];

            }

        }   

        ll ans = 0;

        int flag = 0;

        for(int i=1;i<=n;i++)

        {

            int x = a[i];

            int y = b[i];

            if( y>= maxp)         //有一个怪兽 的防御值 大于等于最大攻击值

            {

                flag = 1;

                break;

            }

            ans += cnt[y][x];       

        }   

        if(!flag)

            printf("%lld\n",ans);   

        else

            puts("-1");                   

    }

    return 0;

}

 

文章评论

程序员必看的十大电影
程序员必看的十大电影
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
鲜为人知的编程真相
鲜为人知的编程真相
如何成为一名黑客
如何成为一名黑客
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员的鄙视链
程序员的鄙视链
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
Java程序员必看电影
Java程序员必看电影
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
我是如何打败拖延症的
我是如何打败拖延症的
代码女神横空出世
代码女神横空出世
编程语言是女人
编程语言是女人
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员和编码员之间的区别
程序员和编码员之间的区别
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
 程序员的样子
程序员的样子
为什么程序员都是夜猫子
为什么程序员都是夜猫子
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
漫画:程序员的工作
漫画:程序员的工作
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
那些争议最大的编程观点
那些争议最大的编程观点
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
一个程序员的时间管理
一个程序员的时间管理
中美印日四国程序员比较
中美印日四国程序员比较
程序员都该阅读的书
程序员都该阅读的书
老程序员的下场
老程序员的下场
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
每天工作4小时的程序员
每天工作4小时的程序员
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有