件数剪枝的调用数

难度：T2

【知识点：搜索与状态】

前置知识：DFS、BFS、数组队列、已学剪枝。

题目描述

按输入顺序对n件正重量物品执行选/不选递归。状态(i,s,c)表示前i件已决定、已选重量s、件数c；初始(0,0,0)。每次进入函数先将calls加1，然后若s>W或c>K或c+(n-i)<K立即返回。若i==n也返回；否则先调用(i+1,s,c)，再调用(i+1,s+w[i],c+1)，这里重量下标从0开始。除此之外不加其他剪枝。只输出上述同时考虑重量与件数剪枝的调用数。进入后立即返回的调用也计数；本题不是输出方案数。

输入格式

第一行n W K。第二行n个正重量；n=0时可省略第二行。

输出格式

一行剪枝调用数。

样例输入

2 1 1
2 3

样例输出

5

样例解释

根计1，不选2后产生两个叶子调用，共3次；选2进入后超重返回计1，总共5。

数据范围

0≤n≤18，0≤W≤100，1≤w[i]≤100。0≤K≤n。