题目链接:http://codeforces.com/contest/369/problem/D
注意题意:所有fools都向编号最小的fool开枪;但每个fool都不会笨到想自己开枪,所以编号最小的fool向编号次小的fool开枪;
所以只需记录编号最小的两位成员即可代表一种状态;当然当只剩一个fool时,次小编号是不存在的出界元素。
编号最小的两个fools只有四种状态:a活b活,a死b死,a活b死,a死b活;注意状态转移条件。
记忆化搜索即可(算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存。)
代码及注释如下:
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <math.h>
#define N 3010
using namespace std;
int p[N],maxp[N];
int vis[N][N]; //访问标记
int n,k,cnt=0;
void dfs(int a,int b,int t){ //a最小,b次小,t记录开枪次数
if(vis[a][b]) return;
vis[a][b]=1;
cnt++;
if(t==k||b>=n) return;
if(p[a]){ //若a的概率不为0,则b就可能killed
if(maxp[b]) dfs(b+1,b+2,t+1); //a,b都killed
if(maxp[b]!=100) dfs(a,b+1,t+1); //b killed
}
//若a的概率不为100,则b就可能living;若b~n的最大概率不为0,则a就可能killed
if(p[a]!=100 && maxp[b]!=0) dfs(b,b+1,t+1);
}
int main()
{
int i,j;
while(scanf("%d %d",&n,&k)!=EOF){
memset(maxp,0,sizeof(maxp));
memset(vis,0,sizeof(vis));
cnt=0;
for(i=0;i<n;i++) scanf("%d",&p[i]);
for(i=n-1;i>=0;i--) maxp[i]=max(maxp[i+1],p[i]); //记录从i至n的最大概率值
dfs(0,1,0);
printf("%d\n",cnt);
}
return 0;
}