阿尔忒弥西娅的「纯情」

笑点解析：这次的博客标题仍然是一个人的名字。

看不懂哥们我写爆搜的。

有一个很简单的搜索，就是你假装一开始是空栈，然后正常搜，每次在空栈的时候决策要不要在一开始的栈中塞入元素，记得如果之前在空栈的时候不塞元素的话，这里就不能塞之前那个点邻接点里有的点。

然后你发现过不了，你写个记忆化把当前节点和栈和 ban 点直接全部塞进去，还是过不了，容易发现 BUG 主要是这个栈的大小可能会搜得很大，但是如果超过了

m

就没意义了（实际判

n

也能过），所以你直接判栈大小超过

m

就退出，然后就过了，比大多数 dp 跑得快。

upd：最新研究表明不判也能过。

代码：

CPP

#include <bits/extc++.h>
using namespace std;
int n, m, k;
int mp[55][25];
int num, T[55][25];

struct dinner {
   int S[105], Top;
   int size() { return Top; }
   void push(int x) { S[Top++] = x; }
   void pop() { S[--Top] = 0; }
   int top() { return S[Top - 1]; }
} stk;

int ans;

__gnu_pbds::gp_hash_table<unsigned long long, int> dp, vis;

unsigned long long base = 999983;
//
int dfs(int cur, int now) {
   if (cur == n) {
      ans = min(ans, now);
      return 0;
   }
   if (now >= ans) return 1e9;
   if (stk.Top > m) return 1e9;
   unsigned long long has = cur;
   for (int i = 0; i <= m; i++) {
      has = has * base + stk.S[i];  //
   }
   for (int i = 1; i <= k; i++) {  //
      if (T[num][i])
         has = has * base + 1;
      else
         has = has * base;
   }
   if (dp.find(has) != dp.end()) {
      ans = min(ans, now + dp[has]);
      return dp[has];  //
   }
   if (vis[has]) return 1e9;
   vis[has] = true;
   int nxt = 1e9;
   if (stk.size() && mp[cur][stk.top()] > -1) {
      int tmp = stk.top();
      stk.pop();
      nxt = min(dfs(mp[cur][tmp], now), nxt);
      stk.push(tmp);
   } else {
      if (!stk.size())
         for (int i = 1; i <= k; i++)
            if (mp[cur][i] > -1) T[num][i]++;
      for (int i = 1; i <= k; i++) {
         if (mp[cur][i] > -1) {
            stk.push(i);
            nxt = min(dfs(mp[cur][i], now), nxt);
            stk.pop();
         }
      }
      if (!stk.size())
         for (int i = 1; i <= k; i++)
            if (mp[cur][i] > -1) T[num][i]--;
      if (!stk.size()) {
         for (int i = 1; i <= k; i++) {
            if (mp[cur][i] > -1 && !T[num][i]) {  //
               num++;
               nxt = min(dfs(mp[cur][i], now + 1) + 1, nxt);
               num--;
            }
         }
      }
   }
   vis[has] = false;
   return dp[has] = nxt;
}
int main() {
   // freopen("nihility.in","r",stdin);
   // freopen("nihility.ouy","w",stdout);
   scanf("%d%d%d", &n, &m, &k);
   memset(mp, -1, sizeof(mp));
   for (int i = 1; i <= m; i++) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      u++, v++, w++;
      mp[u][w] = v;
   }
   ans = n - 1;
   dfs(1, 0);
   printf("%d\n", ans);
   return 0;
}

阿尔忒弥西娅的「纯情」

文章操作

相关推荐

评论

阿尔忒弥西娅的「纯情」