首页 > 其他分享 >P3959 [NOIP2017 提高组] 宝藏

P3959 [NOIP2017 提高组] 宝藏

时间:2024-08-05 11:29:57浏览次数:12  
标签:NOIP2017 int ll long P3959 pair 宝藏 dp define

思路:

考虑状态压缩动态规划。

定义 \(dp_{i,j,S}\) 表示点 \(j\) 离起点 \(i\) 的距离,且从点 \(j\) 开始打通的点集为 \(S\) 的最小代价(注意 \(S\) 不能包含 \(j\))。

考虑枚举 \(S\) 一个一个子集 \(S'\),同时枚举一个 \(k\),需要满足 \(k \in S'\),即我们可以先打通 \(j \to k\),然后由 \(k\) 来打通 \(S'\),由 \(j\) 来打通 \(S \setminus S'\),则状态转移方程为:

\[dp_{i,j,S} = \min\limits_{k \in S' \subseteq S} W(i,k) \times (i+1) + dp_{i+1,k,S' \setminus \{k\}} + dp_{i,j,S \setminus S'} \]

时间复杂度为 \(O(3^nn^3)\)。

注意要先预处理出每个子集状态第一位为 \(1\) 的位置,方便枚举 \(k\),可以用 lowbit 实现。

完整代码:

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const ll N=12,M=(1ll<<N)+10,INF=1e9;
bool Begin;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,m,u,v,w,ans=INF;
ll W[N][N],id[M];
ll dp[N][N][M];
bool End;
int main(){
//	open("A.in","A.out");
	n=read(),m=read();
	for(int i=0;i<n;i++)
	  for(int j=0;j<n;j++)
	    W[i][j]=INF;
	for(int i=0;i<n;i++)
	  for(int j=0;j<n;j++)
	    for(int k=1;k<(1ll<<n);k++)
	      dp[i][j][k]=INF;
	while(m--){
		u=read()-1,v=read()-1,w=read();
		W[u][v]=W[v][u]=min({W[u][v],w});
	}
	for(int x=1,i=0;i<n;i++){
		id[x]=i;
		x<<=1ll;
	}
	for(int i=n-2;i>=0;i--){
		for(int j=0;j<n;j++){
			for(int S=1;S<(1ll<<n);S++){
				if((S>>j)&1ll)
				  continue;		 
				for(int T=S;T;T=(T-1)&S){
					if(dp[i][j][S^T]>=dp[i][j][S])
					  continue;
					for(int G=T;G;G^=lowbit(G)){
						ll k=id[lowbit(G)];
						if(W[j][k]==INF||j==k)
						  continue;
						dp[i][j][S]=min(dp[i][j][S],W[j][k]*(i+1)+dp[i+1][k][T^(1ll<<k)]+dp[i][j][S^T]);						
					}
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	  ans=min(ans,dp[0][i][((1ll<<n)-1)^(1ll<<i)]);
	write(ans);
	return 0;
}

标签:NOIP2017,int,ll,long,P3959,pair,宝藏,dp,define
From: https://www.cnblogs.com/rgw2010/p/18342876

相关文章

  • 发现一个宝藏云服务器,年年都是折扣价,不用四处薅羊毛
    发现一个宝藏云服务器,年年都是折扣价,不用四处薅羊毛,如下:[]==点击这里进入==如果您的朋友正需要一个免费的云服务器,请把链接转发给他#概述云主机(VirtualMachines,VM)是CSDN开发云提供的一种基础计算服务单元,提供处理能力可弹性伸缩的计算服务。云主机涉及多种概念,如下......
  • Luogu P3959 宝藏 题解 [ 紫 ] [ 状压 dp ] [ 二项式定理 ]
    宝藏:一个对着蓝书代码调都能调两个小时的大毒瘤,但是思路还是很值得借鉴的,有普通状压和三进制状压两种做法,或者暴搜剪枝也可以(这里不介绍暴搜剪枝做法)。普通状压做法观察到\(n\le12\),首先想到状压。但考虑到普通的状压不太行,因为\(K\)这个数算在代价里,会导致这个dp有后效......
  • 洛谷-P3869 [TJOI2009] 宝藏
    Abstract传送门本题是状态压缩+记忆化BFS的典型例子。Idea要求从出发点到终点的最短步数,BFS自然是首选的方法,那么,如何构造搜索的每一个节点呢?考虑到机关的数量比较小,最多10种,我们可以考虑用状态压缩去描述机关当前的状态,然后再记录当前的横纵坐标,以及行走的步数即可。值得......
  • P3957 [NOIP2017 普及组] 跳房子
    思路:首先发现单调性,灵活性增加\(x+1\)的答案肯定不会比增加\(x\)的答案更劣。那么可以二分求\(g\),则机器人每次可以移动\([\max(d-mid,1),d+mid]\)这个区间内的距离,为了方便,设为\([l,r]\)。考虑动态规划求得能走到的最大分数,令\(dp_i\)表示走到第\(i\)个格子的最大......
  • 「NOIP2017_Junior」图书管理员
    题目题目描述图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个正整数。每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。小D刚刚当上图书馆的管理员,她......
  • 2024杭电多校4L 寻找宝藏
     设$f_i$表示从1到i节点的最多金币数,$g_i$表示从i到n节点的最多金币数一个矩阵限制了一定区间不能走,同时也规定了只能通过如下四种方法走过来 蓝色表示障碍矩阵,要么在绿色矩阵中选择一个节点x,经过绿色区域一定会避开蓝色矩阵要么从上方的红色区间选择一个点,然后从右方的......
  • 寻找宝藏
    树状数组可以用来维护前缀最大值把矩形按某个坐标排序来处理问题的思想点击查看代码#include<bits/stdc++.h>usingnamespacestd;intp[300005],v[300005],n,m;longlongans[300005],tmp[300005],f[300005],g[300005],h[300005],c[300005];structt1{ intx1,y1,x2......
  • 用这些宝藏AI工具打造副业!实现被动收入!
    前言大家好,我是月月!今天我们来梳理一下在目前的形势下,如何用AI工具打造一个躺赚的副业,实现被动收入?有哪些方法和途径?在本篇文章我主要提供一些已有的AI工具,后面我们再根据具体的AI工具和场景来详细聊聊!1、pyVideoTranspyVideoTrans是一个集成多种功能的视频翻译工具,能够......
  • 透明加密技术分享丨实测十款透明加密软件(宝藏收藏篇)
    小李:“最近公司数据安全问题频发,咱们得找些靠谱的透明加密软件来加强防护。”小王:“没错,我听说市面上有不少优秀的透明加密软件,咱们可以实测一下,挑出最适合咱们公司的。” 于是,他们开始了对十款透明加密软件的实测之旅,以下便是他们的发现与分享。第一款:域智盾基本信息:类......
  • AI视频元年AI漫画推文小众宝藏网站巨日禄体验教程
    2024年可谓AI视频元年,继Sora炸场引发科技圈全球讨论,国外AI圈继续开卷,国内大厂也努力提升视频生成时长和质量。抖音的即梦、快手的可灵、爱诗科技的PixVerse都令人眼前一亮也让我们对国产AI视频有了更多期待!AI视频的出现给影视制作一定会带来挑战和机遇。而对于普通大众小伙伴,......