【洛谷 p2672】推销员
2024-09-05 21:50:19
好了为了凑字数先把题目复制一下:
好了题解第一篇正解:
首先输入,莫得什么好说的:
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",&a[i].s);
for (int i=;i<=n;i++)
scanf("%d",&a[i].v);
然后是思路:
对于每一个x,我们有两种选择:
①选择前x个a值最大的;
②选择前x-1个a值最大的,再在x~n中选择一个s[i]*2+a[i]最大的。
先按照a从大到小排序;
然后数组q[i]记录前i项的a的和;
for (int i=;i<=n;i++)
q[i]=q[i-]+a[i].v;
数组h[i]记录a[i]*2+s[i]后i项的最大值(也就是为了应对情况②)
for (int i=n;i>=;i--)
h[i]=max(h[i+],*a[i].s+a[i].v);
数组qm[i]记录前i项的s的最大值;
for (int i=;i<=n;i++)
qm[i]=max(qm[i-],a[i].s);
答案就是max(q[x]+2*qm[x],q[x-1]+h[x])
对于为什么只取一个后i个,你想啊,只有最远到达的地点的s会对最终答案产生影响,而且其实这里q[x-1]+h[x]并不一定是实际答案,如果前x-1个中s有一个sd大于我们h[i]中取的si,我们本应该用sd来计算答案,但这个题是用si来计算,这样不会对真实的答案造成影响。
最新文章
- 使用技术手段限制DBA的危险操作—Oracle Database Vault
- 初识openstack
- ArcGIS Server 开发之鹰眼地图的实现
- [U3D 导出Xcode工程包,用Xcode给U3D脚本传递参数]
- jiulianhuan 快速幂--矩阵快速幂
- Linux System Log Collection、Log Integration、Log Analysis System Building Learning
- Web Project配置Hirbernate
- release下去除nslog宏
- 感知器Perceptron
- 【转】web测试内容及工具经典总结
- [转载]windows下安装Python虚拟环境virtualenvwrapper-win
- 关于tomcat startup.bat启动后一闪而过的问题(转)
- StringEscapeUtils.unescapeHtml的使用
- React-Native 开发(一) Android环境部署,Hello react-native
- JAVA实用案例之文件导出(JasperReport踩坑实录)
- JAVA写JSON的三种方法,java对象转json数据
- 微信小程序 组件 Demo
- GET 和 POST 的区别 以及为什么 GET请求 比 POST请求 更快
- android 将项目下的数据库拷贝到sd卡中
- Android开发教程 - 使用Data Binding Android Studio不能正常生成相关类/方法的解决办法
热门文章
- @transactional注解在什么情况下会失效,为什么?
- Mongodb的几条命令
- JOI2019 有趣的家庭菜园3
- 未能写入输出文件“c:\Windows\Microsoft.NET\Framework64\v4.0.30319\Temporary ASP.NET Files\......”--“拒绝访问。 ”错误
- (js)粘贴时去掉HTML格式
- jquery 父,子,兄弟节点获取
- handy源码阅读(四):Channel类
- PHP入门培训教程 PHP变量的使用
- [CSP-S模拟测试]:计数(DP+记忆化搜索)
- Java 中如何使用clone()方法克隆对象?