【问题描述】
有n个人坐成一排，这n个人都在某一个小组中，同一个小组的所有人所坐的位置一定是连续的。
有一个记者在现场进行采访，他每次采访都会询问一个人其所在的小组有多少人，被询问的每个人都给出了正确的答案,但是由于时间仓促，记者不一定询问了每个人，我们记录一个长度为n的答案序列，序列的第i个数表示第i个人的回答，如果为0则表示记者没有询问过这个人。
记者发现，对于一些情况，他可以唯一确定这排所有人的分组，而对于另外一些情况则不能，于是记者开始好奇，对于某一个答案序列，他能不能做到这一点，如果能的话输出1，否则输出0。
【数据规模与约定】
对于20%的数据，有1<=n<=15，
对于50%的数据，有1<=n<=100，
对于100%的数据，有1<=n<=1000，1<=T<=50，输入数据中每个答案序列一定由某一组合法的座位分配方案生成。
题解
设f[i]=到i人为止的可行的方案数，然后枚举i人组内人数j，在j可行的情况下，f[i]=sigma(f[i-j])。
由于判断可行性所以f[i]>=2时的意义相同，一律保存为2即可。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 int T,n,a[1005]; 6 int solve() 7 { 8 int f[1005]; 9 memset(f,0,sizeof(f)); 10 f[0]=1; 11 for(int i=1 ; i<=n ; ++i ) 12 for(int j=i,x=0 ; j>=1 ; --j) 13 { 14 if(a[j]) 15 { 16 if(x&&a[j]!=x)break; 17 else x=a[j]; 18 } 19 if(x==0||i-j+1==x) 20 { 21 f[i]=min(2,f[j-1]+f[i]); 22 if(f[i]==2)break; 23 } 24 } 25 if(f[n]==1)return 1; 26 return 0; 27 } 28 int main() 29 { 30 scanf("%d",&T); 31 while(T--) 32 { 33 scanf("%d",&n); 34 for(int i=1 ; i<=n ; ++i) 35 scanf("%d",&a[i]); 36 printf("%d",solve()); 37 } 38 return 0; 39 }