【BZOJ5018】[Snoi2017]英雄联盟
Description
Input
Output
Sample Input
4 4 4
2 2 2
Sample Output
题解:傻题,用f[i]表示花了i块钱最多有多少种展示方案数,然后跑背包DP即可。
一不小心又Rank1了呢~
#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]英雄联盟 背包的更多相关文章
-
BZOJ5018:[SNOI2017]英雄联盟(背包DP)
Description 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤! 小皮球只会玩N个英雄 ...
-
【bzoj5018】[Snoi2017]英雄联盟 背包dp
题目描述 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!小皮球只会玩N个英雄,因此,他也只准 ...
-
BZOJ5018: [Snoi2017]英雄联盟
Description 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不 了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!小皮球只会玩N个英雄 ...
-
BZOJ5018[Snoi2017]英雄联盟——DP
题目描述 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不 了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!小皮球只会玩N个英雄,因此,他也只 ...
-
[BZOJ]5018: [Snoi2017]英雄联盟 DP
[Snoi2017]英雄联盟 Time Limit: 15 Sec Memory Limit: 512 MBSubmit: 270 Solved: 139[Submit][Status][Disc ...
-
bzoj 5018 [Snoi2017]英雄联盟
题面 https://www.lydsy.com/JudgeOnline/problem.php?id=5018 题解 简单的dp 令dp[i][j]表示前i个英雄 总花费为j 最大能够得到的展示种数 ...
-
LOJ——#2256. 「SNOI2017」英雄联盟
https://loj.ac/problem/2256 题目描述 正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」.现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强 ...
-
(转,感谢原作者!)既然选择了Linux,有何必在乎这些——Linux wine国服LOL英雄联盟,完美运行!!
Linux下玩国服LOL,国服哦.网络上随处都可以搜到wine美服LOL的教程,但腾讯运营的国服客户端跟美服原版相差比较大,按照美服的方式不能搞起国服LOL,由于宿舍文化,这几天我专注于wine一个国 ...
-
Android仿掌上英雄联盟首页,实现折叠效果
概述 仿掌上英雄联盟首页的demo 详细 代码下载:http://www.demodashi.com/demo/10695.html 首页大概分为几个部分 状态栏 标题栏 轮播图 切换的Tab 资讯列 ...
随机推荐
-
GCD in Swfit 3.0
这里包括了Queue, Group, Barrier, Semaphore等内容.基本上常用的GCD对象和方法在Swift3.0的改变都囊括其中. 代码在这里:https://github.com/f ...
-
让人又爱又恨的char(字符型)
今天来总结一下char型,平常写算法的时候对这个东西感觉都有一点绕着走,说到底还是对这部分的知识不熟悉所以有点怕他,不过以后不要怕,今天来总结一下 首先,说到字符型数据类型,char型,恩它是一种数据 ...
-
基于visual Studio2013解决C语言竞赛题之0423比赛安排
题目
-
《JavaScript DOM 编程艺术》
前几天京东买了一本书,在豆瓣上好评如潮,买下了啃一啃,书名<JavaScript DOM 编程艺术>,在好好深造一下javaScript.一边啃,一边敲.当然应该要做好笔记.一些简单的就看 ...
-
[十四]JavaIO之PrintStream
功能简介 PrintStream 为其他输出流添加了功能,使它们能够方便地打印各种数据值表示形式 装饰器模式中具体的装饰类 它提供的功能就是便捷的打印各种数据形式 FilterInputStrea ...
-
c# 获取端口的连接数,网站的连接数
端口连接数: public static int PortTcpConnection(int port) { IPGlobalProperties properti = IPGlobalPropert ...
-
C++---使用VS在C++编程中出现 fatal error C1010: 在查找预编译头时遇到意外的文件结尾。是否忘记了向源中添加“#include ";stdafx.h";”?
啦啦啦,好久没写博客啦... 对于C++初学者来说适应一个新的编译器还是需要蛮长一段时间的,现在我就给你们说说标题所说的这个问题吧... 第一步:菜单--〉项目--〉设置,出现“项目设置”对话框,左边 ...
-
laravel架构
1.Laravel 5.1 中的异常处理器和HTTP异常处理实例教程 http://laravelacademy.org/post/1867.html 2.laravel 集成sentry,sentr ...
-
运动目标检测中基于HSV空间的阴影去除算法
在运动目标检测中,常常会出现由于光线被遮挡,或场景其他物体的遮挡,在目标附近或场景里出现阴影,阴影的出现对后期目标的正确分割与处理带了很大的不便.如今,国内外已有不少文献来研究这个问题,并且提出了各种 ...
-
[POI2011]SEJ-Strongbox
题目大意: 一个有密码箱,数字是0~n-1,其中有若干个密码,密码的特点:若x是密码,y是密码,(x可以等于y)则(x+y)%n也是密码. 给一个n(<=10^14),一个k(k<=min ...