P10132

apiad · 2024-02-05 10:03:47 · 题解

博客园。

我们发现直接模拟就好了，在 dfs 中，会有很多个参数。例如：

我们对 dfs 进行剪枝即可。四个参数可以开一个数组来记忆化，但是空间会炸，所以开一个 map。

map<pair<pair<int,int>,pair<int,int> >,bool> mp;

这个记忆化只用记录是否走到，所以是一个 bool 类型。

这样，我们直接暴力模拟即可。轻松 AC！

int n,s;
int q[N], a[N];
struct node{
    int x,d,f,cnt;
};
map<pair<pii,pii>,int> mp;
int ans=0;
int vis[N];
void dfs(int x,int d,int f,int cnt){
    if(x < 1 || x > n) return  ;
    if(q[x] &&!vis[x]&& d >= a[x]){
        vis[x]=1;
        cnt++;
    }
    if(mp.find({{x,d},{f,cnt}}) != mp.end()) return ;
    mp[{{x,d},{f,cnt}}] = 1;
    ans = max(ans,cnt);
    if(q[x]){
        if(f) dfs(x+d,d,f,cnt);
        else dfs(x-d,d,f,cnt);
    }else{
        d += a[x];
        if(f) dfs(x-d,d,!f,cnt);
        else dfs(x+d,d,!f,cnt);
    }
}
void solve() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++)cin >> q[i] >> a[i];
    dfs(s,1,1,0);
    cout<<ans;
}