Codeforces 369(#216 Div2 only) D. Valera and Fools

問題

n人がいて、それぞれ番号が1〜n番である。
全員がピストルとk発の弾をもっていて、k回つぎのことを行う。

自分以外の生存者のうち、番号がもっとも小さい人に向けて同時に銃を撃つ。
i番目の人が撃った銃は、p[i]%の確率で当たる。弾が当たった人は死ぬ。

k回以内（0回も含む）のラウンドが終了した時点における生存者の組み合わせとして、
ありえるのは何通りか、求めよ。

制約条件

n, k≦3000
0≦p[i]≦100

方針

全員の弾は、番号の一番小さい人を狙って、
一番小さい人だけが、二番目に番号の小さい人を狙う。

なので、生き残っている人は、
（ここまで全員死亡）l番目の人、（この間は全員死亡）r番目の人、r+1番目の人…n番目の人
という形になるしかない。

なので、dp[l][r]をその状態に遷移するのに必要なラウンドの回数の最小値というdpをすればいい。
ちょうどk回のラウンドが終わった後の状態と誤読して、なんか面倒なことをやってしまった。

lが生き残るには、r番以降の人にp[i]が100でない人がいる必要がある。
lが死ぬには、r番以降の人にp[i]が0でない人がいる必要がある。

rが生き残るにはp[l]が100でない必要がある。
rが死ぬにはp[i]が0でない必要がある。

ソースコード

const int N = 3010;
int n, k, p[N], sum[N], s[N];

bool dp[N][N][2];
set<pi> ans;

void rec(int l, int r, int f, int rest){
	
	l = min(l, n);
	r = min(r, n);
	
	if(dp[l][r][f]) return;
	dp[l][r][f] = 1;
	
	if(sum[n] - sum[r] == 0) f = 1;
	ans.insert(mp(l, r));
	if(rest == 0) return;
	
	if(p[l] > 0 && s[n] - s[r] > 0) rec(r + 1, r + 2, f, rest - 1); //l, r死ぬ
	if(p[l] > 0 && sum[n] - sum[r] == 0) rec(l, r + 1, f, rest - 1); //r死ぬ
	if(p[l] < 100 && s[n] - s[r] > 0) rec(r, r + 1, f, rest - 1); //l死ぬ
}

int main(){
	
	cin >> n >> k;
	rep(i, n) cin >> p[i];
	
	rep(i, n){
		sum[i + 1] = sum[i] + (p[i] == 100);
		s[i + 1] = s[i] + (p[i] > 0);
	}
	
	rec(0, 1, 0, k);
	cout << ans.size() << endl;
	
	return 0;
}