塔子哥做完了上周的计网实验,但是按照一周一个的原则,他又收到了这周的份额,holy damn!
柜式路由器需要配备接口板才可以工作,接口板用于接入用户业务,且接口板转发能力的和不能大于路由器整机的转发能力。当前某客户订购了2台设备和num块接口板。请计算是否存在一种安装方法,使用户选购的接口板,刚好能装到两台设备上,且每台设备配置的口板的转发能力之和,刚好和整机的转发能力相等。
塔子哥在进行计网实验后,又收到了一周的接口板需求。他需要为两台设备配置接口板,使得每台设备的接口板转发能力之和恰好等于设备的整机转发能力。输入包括目标设备的转发能力、客户订购的接口板数量以及接口板的转发能力列表。若能够满足条件,输出两台设备配置的接口板转发能力列表(需按从小到大排列);若无法满足,则输出-1。
由于题目保证如果存在解,那么解一定是唯一的,所以接口板容量之和肯定是整机转发能力的两倍。
我们可以使用动态规划来解决这个问题,设f[i][j]
表示前i
个接口板能否组成转发能力为j
的整机,如果能组成,那么f[i][j]
定义为i表示第i个元素为结尾接口板,那么我们有状态转移方程: