P1509 找啊找啊找GF

P1509 找啊找啊找GF

题目背景

"找啊找啊找GF,找到一个好GF,吃顿饭啊拉拉手,你是我的好GF.再见."

"诶,别再见啊..."

七夕...七夕...七夕这个日子,对于sqybi这种单身的菜鸟来说是多么的痛苦...虽然他听着这首叫做"找啊找啊找GF"的歌,他还是很痛苦.为了避免这种痛苦,sqybi决定要给自己找点事情干.他去找到了七夕模拟赛的负责人zmc MM,让她给自己一个出题的任务.经过几天的死缠烂打,zmc MM终于同意了.

但是,拿到这个任务的sqybi发现,原来出题比单身更让人感到无聊-_-....所以,他决定了,要在出题的同时去办另一件能够使自己不无聊的事情--给自己找GF.

sqybi现在看中了n个MM,我们不妨把她们编号1到n.请MM吃饭是要花钱的,我们假设请i号MM吃饭要花rmb[i]块大洋.而希望骗MM当自己GF是要费人品的,我们假设请第i号MM吃饭试图让她当自己GF的行为(不妨称作泡该MM)要耗费rp[i]的人品.而对于每一个MM来说,sqybi都有一个对应的搞定她的时间,对于第i个MM来说叫做time[i]. sqybi保证自己有足够的魅力用time[i]的时间搞定第i个MM^_^.

sqybi希望搞到尽量多的MM当自己的GF,这点是毋庸置疑的.但他不希望为此花费太多的时间(毕竟七夕赛的题目还没出),所以他希望在保证搞到MM数量最多的情况下花费的总时间最少.

题目描述

sqybi现在有m块大洋,他也通过一段时间的努力攒到了r的人品(这次为模拟赛出题也攒rp哦~~).他凭借这些大洋和人品可以泡到一些MM.他想知道,自己泡到最多的MM花费的最少时间是多少.

注意sqybi在一个时刻只能去泡一个MM--如果同时泡两个或以上的MM的话,她们会打起来的...

输入输出格式

输入格式:

输入的第一行是n,表示sqybi看中的MM数量.

接下来有n行,依次表示编号为1, 2, 3, ..., n的一个MM的信息.每行表示一个MM的信息,有三个整数:rmb, rp和time.

最后一行有两个整数,分别为m和r.

输出格式:

你只需要输出一行,其中有一个整数,表示sqybi在保证MM数量的情况下花费的最少总时间是多少.

输入输出样例

输入样例#1:

4
1 2 5
2 1 6
2 2 2
2 2 3
5 5

输出样例#1:

13

因为我们不仅让mm的数量多,而且又要时间短,所以要开两个二维数组。

 1 #include<cstring>
 2 #include<algorithm>
 3 #include<cstdio>
 4
 5 using namespace std;
 6
 7 struct mm{
 8     int rmb,rp,ti;
 9 }t[110];
10 int f[110][110];    //mm数量
11 int h[110][110];    //time最小,两个都是money和rp
12 int r,m,n,ans=1e9;
13
14 int main()
15 {
16     scanf("%d",&n);
17     for (int i=1; i<=n; ++i)
18         scanf("%d%d%d",&t[i].rmb,&t[i].rp,&t[i].ti);
19     scanf("%d%d",&m,&r);
20
21     memset(f,0,sizeof(f));
22     memset(h,0,sizeof(h));
23
24     for (int k=1; k<=n; ++k)
25         for (int i=m; i>=t[k].rmb; --i)
26             for (int j=r; j>=t[k].rp; --j)
27             {
28                 if (f[i][j]<f[i-t[k].rmb][j-t[k].rp]+1)
29                 {
30                     f[i][j] = f[i-t[k].rmb][j-t[k].rp]+1;
31                     h[i][j] = h[i-t[k].rmb][j-t[k].rp]+t[k].ti;
32                 }
33                 if (f[i][j]==f[i-t[k].rmb][j-t[k].rp]+1 && h[i][j]>h[i-t[k].rmb][j-t[k].rp]+t[k].ti)
34                     h[i][j] = h[i-t[k].rmb][j-t[k].rp]+t[k].ti;
35             }
36     printf("%d",h[m][r]);
37     return 0;
38 }
时间: 06-14

P1509 找啊找啊找GF的相关文章

python实现自动找茬游戏

http://blog.csdn.net/pipisorry/article/details/46564967 找茬游戏地址[美女大家来找茬] 游戏窗口探查 下载安装PyWin32库(对windows接口的Python封装)http://sourceforge.net/projects/pywin32/,但不能直接点Download图标,不然下下来是一个Readme.txt,点"Browse All Files"寻找需要的版本. 使用spy++找到窗口句柄(或者找到窗口类名lpClas

找工作,公司规模的选择

大多数计算机专业的同学们,毕业后找工作,就是找一份做技术(开发或者测试)的工作,当然也有选择技术支持的. 个人感觉,刚毕业选择开发还是比较好的,选择测试就差了一些,如果选择技术支持,就没有多大的发展空间了,女孩子可以找一个安稳轻松的工作,男孩子还是奋斗拼搏下比较好. 对于技术类型的选择,多数人只是选择Java或者.Net大类,后来会发现,原来.Net还有WCF.MVC之类的细分,之后就越走越深,也距离其他的技术越来越远了.所以,刚毕业的时候,还是避免选择二次开发以及那些偏僻的语言和框架为好,否则

51nod_1831: 小C的游戏(Bash博弈 找规律)

题目链接 此类博弈不需要考虑sg函数,只需要确定必胜态和必败态,解题思路一般为打败先打表找规律,而后找规律给出统一的公式.打表方式:给定初始条件(此题中为ok[0]=ok[1]=0),然后从低到高枚举某一状态的所有次态,若有存在必败次态,则当前状态为必胜态,否则当前状态必败. 题意:对单独一堆石子,支持两种操作:1.石子数-1:2.石子数变为原来石子数的某一因数.取走走后一堆或无法操作(面对n==0,坑啊..)者为负. 先打表找下规律 1 #include<bits/stdc++.h> 2 u

【经验】谈谈怎么找自己想要的资源吧~

[经验]谈谈怎么找自己想要的资源吧~ ?一.先说说找资源: 1.找资源先谷歌,再必应,后好搜,再百度(翻前三页) 很多人谷歌不会上,,,,vpn,代理,或者镜像就可以了 我贴几个镜像:(失效了你就搜一下谷歌镜像) http://www.wow.com/ https://www.ggncr.com/webhp?tab=ww&gws_rd=ssl http://www.xiexingwen.com/ https://g.openibm.com/?newwindow=1&gws_rd=ssl 2

【QT】找茬外挂制作

找茬外挂制作 找茬游戏大家肯定都很熟悉吧,两张类似的图片,找里面的不同.在下眼神不大好,经常瞪图片半天也找不到区别.于是乎决定做个辅助工具来解放一下自己的双眼. 一.使用工具 Qt:主要是用来做界面的 OpenCV: 用于图像处理 C++: 基本实现语言 Qt中OpenCV的配置在[QT]OpenCV配置中讲过了,不会配置的可以看看. 二.实现方案 我要做一个通用的找茬辅助工具,即可以在所有PC找茬游戏中使用.这意味着我们不能通过获取游戏窗口句柄来定位游戏界面.那怎么办呢?灵光一闪,我想到了截图

找纸网:成功复制“找”模式

去年,"互联网+"概念一经提出就被炒得火热,随之获得蓬勃发展的是B2B大宗交易平台,传统行业转型反应之迅速可见一斑.在众多新兴B2B平台中,以找钢网.找纸网(www.zhaozhiw.com)为代表的"找"字模式互联网平台发展最为引人瞩目. 找钢网的成功在业内已经成为标杆,近期更是发布新一轮11亿人民币战略融资.因此它也成为众多涉足B2B创业者的"教科书",在其后陆续涌现出各行业的"找X网"."找纸网"就是

最近听说搞脚本挺爽的 弄了个按键精灵的找图找色

首先你需要下载个按键精灵的软件.如下http://www.anjian.com/ 下好后就打开按键精灵,首先新建一个空白脚本,然后找到抓取按钮. 随便找张图来找色 比如如上这张,用抓取按钮选择右键找到色素点,如#c10b2a 然后将该值放到颜色/图形命令去 在图形找色这里,还有找图功能,其实原理都差不多,都是通过周边像素点的色值来找到符合这个值得点,这样就能找到所选的数据. 当你找到你想得到的句柄(windows的某些你想要获取的窗口)时,就可以通过找色或找图去设置你自己所要的功能.

那年,我们毕业了(纪念找工作的那些日子)

日起日落,过往的一切好像都没有发生似的.只知道,那晚我喝了好多酒,但是没醉:吃了好多菜,但是没饱:说了好多话,但是没哭.就在那种发生而又没有发生的感觉中,我们毕业了,离开了校园,开始了新的生活. 时间倒回2014年的 2月12日,每个人都还沉浸在新年的气氛中时,自己却只身一人提前来到了北京,开始了找工作的旅程.这次旅程,不仅蜕变了自己,也让我明白一个道理:人,都是一样的!(你的想法有时比他人的想法更有价值,相信自己,敢于表达自己.) 与很多毕业生一样,突然从学校走到社会,感觉无从下手,不知道该去

系统谈谈怎样全面做好网站SEO(找富婆)

SEO 英文全称Search Engine Optimization,一般翻译为搜索引擎优化,是目前较为常见的网络推广方式,是一种用来提高网站在搜索引擎排名而提高网站曝光度的一种技术,从而达到提高网站的访问量或者网站的销售量. 目前主流的SEO手段分为两种,站内SEO和站外SEO,下面我就我吴佐强的个人经验来分别谈谈怎样做好一个网站的SEO,从而达到推广自己的网站的目地.(在这里本人吴佐强只谈正规的SEO手段,不会涉及到黑帽SEO.)一.站内SEO[一]代码及标签 首先,做好一个网站的SEO要从

揭秘百度贴吧推荐找富婆流量统计指标

引导语:网站流量统计对站长来说不可或缺的工具,一般站长常用的流量统计工具有cnzz,51la.百度.Google Analytics等,确切的说大部分站长都在使用CNZZ,51la等容易上手的平台,百度.Google Analytics等网站流量统计平台用的站长并不多,究其原因是上手稍微难,尤其是Google Analytics. 现在流量统计平台分两类,网站流量"数据统计平台",只是简单提供数据统计,数据分析挖掘服务没提供,比如CNZZ,51la等平台:网站流量"数据挖掘平