0分全WA

刚学，可能错的比较多qwq

足球队

题目描述

小学中有 $n$ 个班级，每个班级的人数为 $a[i]$ ，也就是全校总共有 $∑a[i]$ 个人。现在老师想从全校选择 $k$ 个人组成足球队，并且老师希望一个班中至少选 $1$ 名同学、至多选 $3$ 个人，请问总共有多少种选择方案。

2个方案不同，当且仅当有至少1个人在其中一个方案里、但不在另一个方案里。由于方案数可能很大，计算过程中对 10007 取模。

输入格式

第一行2个整数 $n,k$

第二行 $n$ 个整数 $a[1...n]$

输出格式

输出一个整数，代表方案数对 10007 取模的值。

样例 #1

样例输入 #1

2 3
2 2

样例输出 #1

4

样例 #2

样例输入 #2

2 3
3 3

样例输出 #2

18

样例 #3

样例输入 #3

5 10
4 7 7 6 9

样例输出 #3

9792

提示

对于30%的数据，$1≤n≤5, 1≤a[i],k≤10$

对于50%的数据，$1≤n≤10, 1≤a[i],k≤20$

对于100%的数据，$1≤n≤2000, 1≤a[i],k≤2000$

#include <bits/stdc++.h>
using namespace std;
int n,shu[2010],k,ans=0;
int dfs(int pos,int lastpeople){
	if(pos==n+1){
		return 1;
	}
	if(lastpeople==0){
		return 0;
	}
	if(shu[pos]==1 && lastpeople==1){
		return (dfs(pos+1,lastpeople-1))%10007;
	}else if(shu[pos]==2 && lastpeople==2){
		return (dfs(pos+1,lastpeople-1)+dfs(pos+1,lastpeople-2))%10007;
	}else{
		return (dfs(pos+1,lastpeople-1)+dfs(pos+1,lastpeople-2)+dfs(pos+1,lastpeople-3))%10007;
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>shu[i];
	}
	cout<<dfs(1,k);
	return 0;
}
//dfs 1 3

//dfs 2 2
//dfs 2 1

//dfs 3 1
//dfs 3 0
//dfs 3 0

//ab
//AB

//a AB
//b AB
//ab A
//ab B