cf D. Valera and Fools

http://codeforces.com/contest/369/problem/D

标号最小的两个人会有四种状态：a活b活，a死b活，a活b死，a死b死；按照这四种状态dfs就可以求出最后的数量。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 5000
 5 using namespace std;
 6 
 7 int n,k;
 8 int ans;
 9 int p[maxn];
10 bool vis[maxn][maxn];
11 int c[maxn];
12 
13 void dfs(int num1,int num2,int cnt)
14 {
15     if(vis[num1][num2]) return ;
16     vis[num1][num2]=true;
17     ans++;
18     if(num2>n||cnt==k) return;
19     if(p[num1])
20     {
21         if(c[num2]) dfs(num2+1,num2+2,cnt+1);
22         if(c[num2]<100) dfs(num1,num2+1,cnt+1);
23     }
24     if(p[num1]!=100)
25     {
26         if(c[num2]) dfs(num2,num2+1,cnt+1);
27     }
28 }
29 
30 int main()
31 {
32     while(scanf("%d%d",&n,&k)!=EOF)
33     {
34         ans=0;
35         memset(vis,false,sizeof(vis));
36         memset(p,0,sizeof(p));
37         memset(c,0,sizeof(c));
38         for(int i=1; i<=n; i++)
39         {
40             scanf("%d",&p[i]);
41         }
42         for(int i=n; i>=1; i--)
43         {
44             c[i]=max(c[i+1],p[i]);
45         }
46         dfs(1,2,0);
47         printf("%d
",ans);
48     }
49     return 0;
50 }

View Code