luogu P3959 [NOIP2017 提高组] 宝藏
2021/10/5 23:13:05
本文主要是介绍luogu P3959 [NOIP2017 提高组] 宝藏,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题面传送门
遇到这种按路径长度计算代价的考虑分层。
设\(f_{i,j}\)为树高为\(i\),包含了集合为\(j\)的答案的最小答案。
考虑枚举最后一层是什么,然后从前面转移。
每个最后一层的点从前面所有点中找到最优的点连接上去。
但是其实不是每个点连的边都是最后一层的。
其实如果不是最后一层只会让答案变劣,会在迭代的时候去除掉,所以这个dp是正确的。
时间复杂度\(O(3^nn^3)\)勉强跑过。
code:
#include<bits/stdc++.h> #define I inline #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define abs(x) ((x)>0?(x):-(x)) #define re register #define RI re int #define ll long long #define db double #define lb long db #define N 12 #define M (1<<N) #define mod 1000000007 #define Mod 998244352 #define eps (1e-4) #define U unsigned int #define it iterator #define Gc() getchar() #define Me(x,y) memset(x,y,sizeof(x)) #define d(x,y) (n*(x-1)+(y)) #define R(n) (rand()*rand()%(n)+1) using namespace std; int n,m,k,A[N+5][N+5],now,B[N+5],Bh,x,y,z;ll dp[N+5][M+5],Ans=1e9; I ll calc(int x,int y){ RI i,j;ll ToT=0,now=0;Bh=0;for(i=1;i<=n;i++) (x>>i-1)&1&&(B[++Bh]=i); for(i=1;i<=n;i++){ if(!((y>>i-1)&1))continue;now=1e9;for(j=1;j<=Bh;j++) now=min(now,A[i][B[j]]);ToT+=now; }return ToT; } int main(){ // freopen("1.in","r",stdin); RI i,j,h;Me(A,1);Me(dp,1);scanf("%d%d",&n,&m);k=(1<<n);for(i=1;i<=m;i++) scanf("%d%d%d",&x,&y,&z),A[x][y]=A[y][x]=min(A[x][y],z);for(i=1;i<=n;i++) dp[1][1<<i-1]=0; for(i=2;i<=n;i++){ for(j=0;j<k;j++){ for(h=j;h;h=(h-1)&j) now=calc(j^h,h),dp[i][j]=min(dp[i-1][j^h]+now*(i-1),dp[i][j]); }Ans=min(Ans,dp[i][k-1]); }printf("%lld\n",(n==1?0:Ans)); }
这篇关于luogu P3959 [NOIP2017 提高组] 宝藏的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南