P4206 [NOI2005] 聪聪与可可——期望，记搜

· · 个人记录

思路

初见思路就是没有思路

看了 10min 没有想法，果断暴力模拟（其实有一点隐约的想法，但是形成不了解法）

暴力

注意到没有边权，可以用bfs求出点两两之间的距离

由于 n 只有 10^3 ，可以直接 n^2 把点之间的距离求出来

然后再考虑聪聪会跳到的点

可以想到直接把会跳到的点存起来，计算时间是 O(n^2) 级别的（因为事实上边数只有 10^3 ，并没有到 n^3 的级别）

接下来就可以暴搜了，可以写成返回值的模式就尽量写成这样，如果后面想到记忆化可以用上

最初是想 3 个参数，老鼠的节点，猫的节点，时间

于是就可以暴力拿到 50pts （其实有 70pts ）

记搜

考虑优化搜索，当然目前三个参数的搜索是记忆化不了的

看看哪个可以压掉

答案是时间维，因为在转移过程中用到的时间流逝可以加在返回值所在的表达式里（此时状态已经发生改变了，所以不太好想）

也就是原先的 dfs(mouse,time+1,cat) 变成 dfs(mouse,cat)+1 ，这样就可以压掉一维了

于是就可以愉快地记忆化了

（话说回来我好像就没想过dp，这是一个问题）

也就是说如果一个状态在转移过程中并没有和其他的环境产生紧密的联系，那么它就可能是可以被压掉的那个量

AC Code:

#include <bits/stdc++.h>
#define db double
using namespace std;

const int MAXN=1e3+5;
const db eps=1e-17;

int nxt[MAXN][MAXN],dis[MAXN][MAXN];
db dp[MAXN][MAXN];
vector<int > edge[MAXN];
bool vis[MAXN];
list<int > q;
int n,m;

void bfs(int s){
    memset(vis,0,sizeof(vis));
    dis[s][s]=0;
    q.push_back(s);
    int u;vis[s]=1;
    while(!q.empty()){
        u=q.front();q.pop_front();
        for(auto v:edge[u]){
            if(vis[v]) continue;
            dis[s][v]=dis[s][u]+1;
            vis[v]=1;
            q.push_back(v);
        }
    }
}//

int geted(int u,int c){
    if(nxt[c][u]) c=nxt[c][u];
    else{
        if(c==u) return u;
        for(auto v:edge[c])
            if(dis[v][u]==dis[c][u]-1){nxt[c][u]=v;c=v;break;}
    }
    if(nxt[c][u]) c=nxt[c][u];
    else{
        if(c==u) return u;
        for(auto v:edge[c])
            if(dis[v][u]==dis[c][u]-1){nxt[c][u]=v;c=v;break;}
    }
    return c;
}//

db dfs(int u,int c){
    if(dis[u][c]<=2) return 0.0;
    if(abs(dp[u][c])>=eps) return dp[u][c];
    int cc=c;
    c=geted(u,c);
    db res=0.0;
    for(auto v:edge[u]){
        if(c==v) continue;
        else res+=(dfs(v,c)+1.0)/(db)(edge[u].size()+1.0);
    }
    res+=(dfs(u,c)+1.0)/(db)(edge[u].size()+1.0);
    dp[u][cc]=res;
    return res;
}//

int cat,mouse;

void work(){
    scanf("%d%d",&n,&m);
    scanf("%d%d",&cat,&mouse);
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    for(int i=1;i<=n;++i){
        sort(edge[i].begin(),edge[i].end());
        bfs(i);
    }

    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            dp[i][j]=0.0;

    printf("%.03lf",dfs(mouse,cat)+1);
}//

int main(){
    work();
    return 0;
}