【BZOJ5018】[Snoi2017]英雄联盟 背包

时间:2022-12-10 11:45:06

【BZOJ5018】[Snoi2017]英雄联盟

Description

正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」。现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!小皮球只会玩N个英雄,因此,他也只准备给这N个英雄买皮肤,并且决定,以后只玩有皮肤的英雄。这N个英雄中,第i个英雄有Ki款皮肤,价格是每款CiQ币(同一个英雄的皮肤价格相同)。为了让自己看起来高大上一些,小皮球决定给同学们展示一下自己的皮肤,展示的思路是这样的:对于有皮肤的每一个英雄,随便选一个皮肤给同学看。比如,小皮球共有5个英雄,这5个英雄分别有0,0,3,2,4款皮肤,那么,小皮球就有3*2×4=24种展示的策略。现在,小皮球希望自己的展示策略能够至少达到M种,请问,小皮球至少要花多少钱呢?

Input

第一行,两个整数N,M
第二行,N个整数,表示每个英雄的皮肤数量Ki
第三行,N个整数,表示每个英雄皮肤的价格Ci
共 10 组数据,第i组数据满足:N≤max(5,(log2i)^4) M≤10^17,1≤Ki≤10,1≤Ci≤199。保证有解

Output

一个整数,表示小皮球达到目标最少的花费。

Sample Input

3 24
4 4 4
2 2 2

Sample Output

18

题解:傻题,用f[i]表示花了i块钱最多有多少种展示方案数,然后跑背包DP即可。

一不小心又Rank1了呢~

【BZOJ5018】[Snoi2017]英雄联盟 背包

#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n,mx,ans;
int w[130],c[130];
ll m,f[250000];
inline ll rd()
{
ll ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd();
int i,j,k;
for(i=1;i<=n;i++) w[i]=rd();
for(i=1;i<=n;i++) c[i]=rd();
f[0]=1,ans=1<<30;
if(m<=1)
{
printf("0");
return 0;
}
for(i=1;i<=n;i++)
{
if(w[i]<=1) continue;
mx+=w[i]*c[i];
for(j=min(ans,mx);j>=2*c[i];j--)
{
for(k=2;k<=w[i]&&k*c[i]<=j;k++) f[j]=max(f[j],f[j-k*c[i]]*k);
if(f[j]>=m) ans=j;
}
}
printf("%d",ans);
return 0;
}

【BZOJ5018】[Snoi2017]英雄联盟 背包的更多相关文章

  1. BZOJ5018&colon;&lbrack;SNOI2017&rsqb;英雄联盟&lpar;背包DP&rpar;

    Description 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤! 小皮球只会玩N个英雄 ...

  2. 【bzoj5018】&lbrack;Snoi2017&rsqb;英雄联盟 背包dp

    题目描述 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!小皮球只会玩N个英雄,因此,他也只准 ...

  3. BZOJ5018&colon; &lbrack;Snoi2017&rsqb;英雄联盟

    Description 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不 了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!小皮球只会玩N个英雄 ...

  4. BZOJ5018&lbrack;Snoi2017&rsqb;英雄联盟——DP

    题目描述 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不 了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!小皮球只会玩N个英雄,因此,他也只 ...

  5. &lbrack;BZOJ&rsqb;5018&colon; &lbrack;Snoi2017&rsqb;英雄联盟 DP

    [Snoi2017]英雄联盟 Time Limit: 15 Sec  Memory Limit: 512 MBSubmit: 270  Solved: 139[Submit][Status][Disc ...

  6. bzoj 5018 &lbrack;Snoi2017&rsqb;英雄联盟

    题面 https://www.lydsy.com/JudgeOnline/problem.php?id=5018 题解 简单的dp 令dp[i][j]表示前i个英雄 总花费为j 最大能够得到的展示种数 ...

  7. LOJ——&num;2256&period; 「SNOI2017」英雄联盟

    https://loj.ac/problem/2256 题目描述 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强 ...

  8. &lpar;转,感谢原作者!&rpar;既然选择了Linux&comma;有何必在乎这些——Linux wine国服LOL英雄联盟,完美运行!!

    Linux下玩国服LOL,国服哦.网络上随处都可以搜到wine美服LOL的教程,但腾讯运营的国服客户端跟美服原版相差比较大,按照美服的方式不能搞起国服LOL,由于宿舍文化,这几天我专注于wine一个国 ...

  9. Android仿掌上英雄联盟首页,实现折叠效果

    概述 仿掌上英雄联盟首页的demo 详细 代码下载:http://www.demodashi.com/demo/10695.html 首页大概分为几个部分 状态栏 标题栏 轮播图 切换的Tab 资讯列 ...

随机推荐

  1. GCD in Swfit 3&period;0

    这里包括了Queue, Group, Barrier, Semaphore等内容.基本上常用的GCD对象和方法在Swift3.0的改变都囊括其中. 代码在这里:https://github.com/f ...

  2. 让人又爱又恨的char&lpar;字符型&rpar;

    今天来总结一下char型,平常写算法的时候对这个东西感觉都有一点绕着走,说到底还是对这部分的知识不熟悉所以有点怕他,不过以后不要怕,今天来总结一下 首先,说到字符型数据类型,char型,恩它是一种数据 ...

  3. 基于visual Studio2013解决C语言竞赛题之0423比赛安排

       题目

  4. 《JavaScript DOM 编程艺术》

    前几天京东买了一本书,在豆瓣上好评如潮,买下了啃一啃,书名<JavaScript DOM 编程艺术>,在好好深造一下javaScript.一边啃,一边敲.当然应该要做好笔记.一些简单的就看 ...

  5. &lbrack;十四&rsqb;JavaIO之PrintStream

    功能简介   PrintStream 为其他输出流添加了功能,使它们能够方便地打印各种数据值表示形式 装饰器模式中具体的装饰类 它提供的功能就是便捷的打印各种数据形式 FilterInputStrea ...

  6. c&num; 获取端口的连接数,网站的连接数

    端口连接数: public static int PortTcpConnection(int port) { IPGlobalProperties properti = IPGlobalPropert ...

  7. C&plus;&plus;---使用VS在C&plus;&plus;编程中出现 fatal error C1010&colon; 在查找预编译头时遇到意外的文件结尾。是否忘记了向源中添加&OpenCurlyDoubleQuote;&num;include &quot&semi;stdafx&period;h&quot&semi;”&quest;

    啦啦啦,好久没写博客啦... 对于C++初学者来说适应一个新的编译器还是需要蛮长一段时间的,现在我就给你们说说标题所说的这个问题吧... 第一步:菜单--〉项目--〉设置,出现“项目设置”对话框,左边 ...

  8. laravel架构

    1.Laravel 5.1 中的异常处理器和HTTP异常处理实例教程 http://laravelacademy.org/post/1867.html 2.laravel 集成sentry,sentr ...

  9. 运动目标检测中基于HSV空间的阴影去除算法

    在运动目标检测中,常常会出现由于光线被遮挡,或场景其他物体的遮挡,在目标附近或场景里出现阴影,阴影的出现对后期目标的正确分割与处理带了很大的不便.如今,国内外已有不少文献来研究这个问题,并且提出了各种 ...

  10. &lbrack;POI2011&rsqb;SEJ-Strongbox

    题目大意: 一个有密码箱,数字是0~n-1,其中有若干个密码,密码的特点:若x是密码,y是密码,(x可以等于y)则(x+y)%n也是密码. 给一个n(<=10^14),一个k(k<=min ...