// [题意]
// n辆车按顺序安排在一个渡口的左边或右边,不超过渡口长度最多放多少辆
// 相当于n个物品按顺序尽量多地放在两个相同容量的背包里
// 如果放不下后面的就不放了,题目还要求输出要放的车都放哪边?记录路径即可
// 由于是按顺序放,所以第i辆车放的话,i前面的车必然已经放好了,不可能不放
// [解题方法]
// dp[i][j]=1 表示左边车占了j长度时,可以放i辆车
// 设前i辆车总长度为sum[i],则:
// 对于dp[i][j]左边占了j长度,右边就必然占了sum[i]-j的长度了
// dp[i][j]=0 表示这种状态不可行
// 设V为公路长度,w[i]为第i辆车的长度,状态转移如下:(0<=j<=V)
// dp[i][j] = (j>=w[i]&&dp[i-1][j-w[i]]) || (sum[i]-j<=V&&dp[i-1][j])
// 放左边 放右边
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define LL long long
#define N 2005
#define M 10005
#define inf 0x3fffffff
int dp[N][M], w[N], sum[N];
int pre[N][M], ans[N];
int main()
{
int t, i, j, k, V, n, vj;
cin >> t;
while (t--)
{
cin >> V;
V *= 100;
memset (dp, 0, sizeof(dp));
dp[0][0] = 1;
n = 0;
sum[0] = 0;
while(cin >> k, k)
{
++n;
w[n] = k;
sum[n] = sum[n-1] + k;
}
vj = -1;
for (i = 1; i <= n; i++)
{
for (j = 0; j <= V; j++)
{
if (j >= w[i] && dp[i-1][j-w[i]]) {
k = i;
vj = j;
dp[i][j] = 1;
pre[i][j] = j-w[i];
} else if (sum[i]-j <= V && dp[i-1][j]) {
k = i; //更新最大能放的车辆数
vj = j;
dp[i][j] = 1;
pre[i][j] = j; //记录路径
}
}
}
i = k;
while (i--)
{
j = pre[i+1][vj];
if (j == vj) ans[i] = 1;
else ans[i] = 0;
vj = j;
}
cout << k << endl;
for (i = 0; i < k; i++)
{
if (ans[i]) puts ("starboard");
else puts ("port");
}
if (t) puts("");
}
return 0;
}
分享到:
相关推荐
开源软件ferry是集工单统计、任务钩子、权限管理、灵活配置流程与模版等等于一身的开源工单系统,当然也可以称之为工作流引擎。 致力于减少跨部门之间的沟通,自动任务的执行,提升工作效率与工作质量,减少不必要的...
ferry工单系统文件2021.8.20
前端开源库-vigour-ferryVigor Ferry,推送新的时间戳,以便通知应用程序更新。
Ferry 是(又一个)REST API 框架。 用法 通常,在创建服务器实现时,需要 Ferry 作为依赖项。 请参阅。 引擎 引擎为渡轮提供动力; 它们是提供各种功能的第三方模块。 为了创建功能性 API,每种类型都需要一个引擎...
还不错的计算机图形学教程
ferry - 一个数据迁移和可视化的命令行Ruby gem
一个简单的U盘摆渡代码,仅供学习参考,请勿用于其他用途
data ferry control mostly focuses on predetermined ferry routes, assuming full observations at the ferry and no explicit Quality of Service (QoS) constraints on the resulting communications. In this ...
Ferry:使用 Docker 的大数据开发环境Ferry 可让您在 AWS、OpenStack 和本地机器上启动、运行和管理大数据集群。 它通过利用诸如类的技术来做到这一点。 渡轮目前支持: Hadoop/YARN(版本 2.5.1) 卡桑德拉(2.1.0 ...
ferry工单系统 v1.0.zip
渡船 耶鲁课程和评估数据的搜寻器。... /ferry/includes :整个Ferry使用的辅助功能。 /ferry/migration :我们用于将旧数据库(2020年夏季之前)迁移到当前数据库的脚本。 不再维护,但保留以防万一。
为更贴近机会网络的实际应用,...DF算法是通过调度所有ferry的运动来实现ferry之间的直接通信,从而实现网络的区间通信。通过DF算法和使用中继节点的ferry路由算法的对比,得出DF算法能够有效降低网络的平均传输时延。
migrate -source file://migrations -database " postgres://stefanchurch@localhost:5432/ferry-services?sslmode=disable " up 要进行向下迁移: migrate -source file://migrations -database " postgres://...
python库。资源全名:ferry-0.2.4.tar.gz
基于Gin + Vue + Element UI前后端分离的工单系统 流程中心 通过灵活的配置流程、模版等数据,非常快速方便的生成工单流程,通过对流程进行任务绑定,实现流程中的钩子操作,目前支持绑定邮件来通知处理,当然为兼容...
python库。资源全名:ferry-0.1.22.tar.gz
轮渡(工作进行中) 目标 提供管理实用程序以从FoundationDB导入和导出数据。 非目标 该实用程序并非旨在替代出色的fdbbackup工具。我们不尝试复制或遵循foundationdb突变日志。由于事务限制为5秒,因此我们也无法在...
Korn Ferry:热忱铸就成功—员工敬业度如何推动企业成功.rar
Ferry 是一个可定制的源代码编辑组件; 主要特点: 100% Unicode 支持 - 处理 LTR、RTL(希伯来语、阿拉伯语)脚本; 语法高亮(使用外部引擎); 可变高度的文本行; 方便的API等
某汽车轮渡口,有n辆车要过河。n辆车只有两种要么是客车,要么是货车。已知过江渡船每次能载10辆车,从0分开始每10分钟来一次(即0分一辆,10分一辆,以此类推)。又知上渡船要遵守下述规定:若x分来了一辆渡船所有...