ZOJ 3956 Course Selection System
2024-08-25 07:56:17
题意
有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之类的吗(雾~
然后改一下滚动数组,代码比较短。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
typedef long long LL;
const int maxn=+;
int T,n,M;
LL C[maxn],H[maxn];
LL f[+]; int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
M=;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d%d",&H[i],&C[i]);
M+=C[i];
}
memset(f,,sizeof(f));
for(int i=;i<=n;i++){
for(int j=M;j>=C[i];j--){
f[j]=max(f[j],f[j-C[i]]+H[i]);
}
}
LL ans=;
for(int i=;i<=M;i++)
ans=max(ans,f[i]*f[i]-f[i]*i-i*i);
printf("%lld\n",ans);
}
return ;
}
最新文章
- JavaScript语言精粹--执行环境及作用域,this
- Windows Phone Sliding Effect
- javascript - 浏览器对象
- TL-WR703 USB不稳定/当前的总结
- Function 1 - hello world
- 让DataGridView显示行号
- 反射---Java高级开发必须懂的
- javascript 路线整理
- SQLHelper简单版(基础版)
- python_特殊函数
- 【Teradata TTU】Windows TTU安装工具列表
- Vue使用过程中常见问题
- 校园电商项目4——SSM各项配置
- Java归并排序的递归与非递归实现
- vim块编辑删除、插入、替换【转】
- 前端图片缓存之通过img标签加载GIF只能播放一次问题(转载)
- centos7 防火墙 开启端口 并测试
- 使用easyui实现双击列表中某个值直接对其进行修改
- tomcat站点配置
- table切换(自己写)