这道题难点在于状态设计。考虑线性 DP,设 dpidp_idpi 为仅考虑前 iii 个地雷且钦定第 iii 个不引爆的方案数。这样设计的好处在于 iii 前面的地雷一定不会引爆 iii 后面的,从而满足无后效性。
注意需要在左右无穷远处各添加一个爆炸半径无穷大的哨兵地…
include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=25;
int n;
vectorwords;
int cnt[N];
char st;
int ans=0;
void dfs(string cur){
ans=max(ans,(int)cur.size());
for(int i…