文档章节

ZOJ 3956 Course Selection System

o
 osc_z1hvg4cu
发布于 2018/04/24 18:33
字数 514
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题意

  有n节课可供选择,每节课都有两个值Hi和Ci,如果学生选择了m节课(x1,x2,....,xm),则它的舒适值被定义为:

  //这里没有公式((lll¬ω¬)),因为那个图片我保存不下来≧ ﹏ ≦,见原题好啦~

分析

  当时被这个公式搞得很懵逼,场上想了几种贪心发现都能找出反例。结束后听学长们说是个背包。。。一脸懵逼。

  我们在来看这个题···我们发现Ci比Hi小很多··这里算是一个暗示o(* ̄▽ ̄*)o

  我们再来看那个公式我们可以发现,当 C一定时,H越大这个舒适值越大。而对于每一节课我们都只有两种决策,选或者不选。那么我们就可以把这个问题转化为背包啦~

  我们定义f[i][j]=这个状态下最大的H值。我们按照背包的套路,把课作为阶段,把C定义为状态。

  那么转移也很显然

  f[i][j]=max(f[i-1][j],f[i-1][j-C[i]]+H[i])

  但是等等,这样提交并不能AC而是会Segmentation Fault,很懵逼,怎么改也不对。然后去查了题解,发现去要用滚动数组。ZOJ什么鬼啊!!这种情况不应该提示MLE之类的吗(雾~

  然后改一下滚动数组,代码比较短。

  

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 const int maxn=500+10;
 9 int T,n,M;
10 LL C[maxn],H[maxn];
11 LL f[50000+10];
12 
13 int main(){
14     scanf("%d",&T);
15     for(int t=1;t<=T;t++){
16         M=0;
17         scanf("%d",&n);
18         for(int i=1;i<=n;i++){
19             scanf("%d%d",&H[i],&C[i]);
20             M+=C[i];
21         }
22         memset(f,0,sizeof(f));
23         for(int i=1;i<=n;i++){
24             for(int j=M;j>=C[i];j--){
25                 f[j]=max(f[j],f[j-C[i]]+H[i]);
26             }
27         }
28         LL ans=0;
29         for(int i=0;i<=M;i++)
30             ans=max(ans,f[i]*f[i]-f[i]*i-i*i);
31         printf("%lld\n",ans);
32     }
33 return 0;
34 }
View Code

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

告别传统机房:3D 机房数据可视化实现智能化与VR技术的新碰撞

前言 随着各行业对计算机依赖性的日益提高,计算机信息系统的发展使得作为其网络设备、主机服务器、数据存储设备、网络安全设备等核心设备存放地的计算机机房日益显现出它的重要地位,而机房...

xhload3d
昨天
13
0
如何使用.css()应用!important? - How to apply !important using .css()?

问题: I am having trouble applying a style that is !important . 我在应用!important样式时遇到麻烦。 I've tried: 我试过了: $("#elem").css("width", "100px !important"); This doe......

富含淀粉
昨天
5
0
spring源码解析-xml配置文件读取

整个 XML配置文件读取的大致流程如下: 通过继承自AbstractBeanDefinitionReader中的方法,来使用ResourLoader将资源文件路径转换为对应的Resource文件(读取资源文件并将其转为Resource) ...

wc_飞豆
昨天
16
0
salesforce community cloud 1

NO.1 Universal Containers has a Community for their partners. They would like to add a new partner company and grant their users access to the Community. What is the first step ......

jinzongyu
昨天
11
0
如何使用PHP计算两个日期之间的差异? - How to calculate the difference between two dates using PHP?

问题: I have two dates of the form: 我有两个日期格式: Start Date: 2007-03-24 End Date: 2009-06-26 Now I need to find the difference between these two in the following form:......

技术盛宴
昨天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部