ZaakDov上高中时经常中午跑出去打魔兽，下午上课总是踩铃。由于每次上课总是匆匆忙忙跑进教室的，所以他需要训练一番不凡的爬楼梯技术。
又是一次快速爬楼梯练习，不过这次竟然出现了楼梯上有水果皮的场景，这让ZaakDov不得不选择以那些楼梯为落脚点（否则踩上去回摔跟头的哟，在楼梯上 摔跟头时可是件很惨的事情）。喜爱数学的他早已知道没有水果皮时应有多少种爬楼梯方法，但是这次有了水果皮就得自己推算了。
现在想推测一下一共有多少种爬楼梯方法。
假设他一次能迈出1到p步阶梯，共有n步阶梯，保证楼梯最后一步阶梯没有水果皮。
你能判断出有多少种爬法吗？
Input
多组测试数据。
每组第一行三个整数n,m,p(1<=n<=1000,1<=m<=n-1,1<=p<=n)，接下来m行每行一个整数x，表示第x阶楼梯上有水果皮，同一组测试数据中不会出现两个或两个以上相同的x。
输入以3个-1结束。
Output
对每组测试数据输出其结果（共有多少种爬楼梯方法）。
最后3个-1不用处理。
Sample Input
3 1 3
2
3 0 2
3 1 2
2
4 0 3
-1 -1 -1
Sample Output
2
3
1
7
两个解法：
dfs超时。
换dp过的
/*
* dfs TLE, try dp again, see 1546b.c
* */
#include
#include
int fruit[1010], count;
int n, m, p;
void dfs(int current)
{
if (current > n)
return;
if (fruit[current] == 1)
return;
count++;
int i;
for (i=1 ; i
{
dfs(current + i);
}
}
int main(int argc, char *argv[])
{
int i, t;
while (scanf("%d %d %d", &n, &m, &p))
{
if (-1 == n && -1 == m && -1 == p)
break;
memset(fruit, 0, sizeof(fruit));
count = 0;
for (i=0 ; i
scanf("%d", &t);
fruit[t] = 1;
}
dfs(1);
printf("%d\n", count);
}
}
/* 很简单的dp,注意输出是long long，初始化条件method[0]=1 */
#include
#include
int fruit[1010];
long long method[1010];
long long dp(int n, int p)
{
int i, j;
for (i=1 ; i<=n ; i++)
{
for (j=i-p ; j {
if (j < 0 || 1 == fruit[j] || 1 == fruit[i])
continue;
method[i] += method[j];
}
}
return method[n];
}
int main(int argc, char *argv[])
{
int n, m, p, i, t;
while (scanf("%d %d %d", &n, &m, &p))
{
if (-1 == n && -1 == m && -1 == p)
break;
memset(fruit, 0, sizeof(fruit));
memset(method, 0, sizeof(method));
method[0] = 1;
for (i=0 ; i
scanf("%d", &t);
fruit[t] = 1;
}
printf("%lld\n", dp(n, p));
}
}