NOIP2017 宝藏

Author Avatar
空気浮遊 2018年03月26日
  • 在其它设备中阅读本文章
  • 状压dp
  • NOIP
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

Problem

请查看原题面。

Solution

参考的 Solution:https://www.luogu.org/blog/user50971/solution-p3959

这题真的有点玄学。

状压是状压,但是记忆化搜索.... 没有体现利用了已经得到状态的过程。

也就是说记忆化搜索同样可以应用于剪枝。这应该算是一种剪枝类型的记忆化搜索,又或者是类 SPFA-DFS 顺序 dp。

分析一下复杂度。
假设状态 i 转移到状态 j,新增点 x,需要枚举边 (y,x)。y 有 n 种情况。
可以转移到状态 j 的状态共有 n 种,因此状态 j 理论上最多被更新 $n^2$ 次。
但若转移到状态 j 的状态再次被更新(非拓扑序 dp 可能遇见的情况),则状态 j 理论上最多被更新的次数 $>n^2$。

所以综上,理论最优复杂度 $O(n^32^n)$ -> $O(kn^32^n)$ -> $O(玄学 / 能过)$。

Code

// Code by ajcxsu
// Problem: Treasure

#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;

int n,m;
int E[13][13];
int f[1<<14];
int dis[13];
int U;

void dfs(int x) {
    if(x==U) return;
    for(int i=0;i<n;i++)
        if((1<<i)&x)
            for(int j=0;j<n;j++)
                if(E[i][j]!=INF && !((1<<j)&x))
                    if(f[x|(1<<j)] > E[i][j]*dis[i]+f[x]) {
                        int tmp=dis[j];
                        dis[j]=dis[i]+1;
                        f[x|(1<<j)]=E[i][j]*dis[i]+f[x];
                        dfs(x|(1<<j));
                        dis[j]=tmp;
                    }
}

int main() {
    memset(E,0x3f,sizeof(E));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    U=1<<n, U--;
    int u,v,w;
    for(int i=1;i<=m;i++) cin>>u>>v>>w, u--,v--, E[v][u]=E[u][v]=min(E[u][v],w);
    int ans=0x3f3f3f3f;
    for(int i=0;i<n;i++) {
        memset(f,0x3f,sizeof(f));
        memset(dis,0x3f,sizeof(dis));
        f[1<<i]=0, dis[i]=1;
        dfs(1<<i);
        ans=min(ans, f[U]);
    }
    cout<<ans<<endl;
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/noip-2017-treasure.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • May 2025 1
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 31
    • August 2018 18
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 281
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material