关键词:
有一个送外卖的,他手上有n份订单,他要把n份东西,分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发,然后n个城市都要走一次(一个城市可以走多次),最后还要回到0点(他的单位),请问最短时间是多少。现在已知任意两个城市的直接通路的时间。
第一行一个正整数n (1<=n<=15)
接下来是一个(n+1)*(n+1)的矩阵,矩阵中的数均为不超过10000的正整数。矩阵的i行j列表示第i-1号城市和j-1号城市之间直接通路的时间。当然城市a到城市b的直接通路时间和城市b到城市a的直接通路时间不一定相同,也就是说道路都是单向的。
一个正整数表示最少花费的时间
3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0
8
1<=n<=15
试题分析:额,这题数据有BUG,N=15,数据输入了一个15*15的矩阵而不是16*16的……
我们设dp[i][j]表示现在走到了i,当前状态为j的最小值
那么就有dp方程:
dp[j][i]=min(dp[j][i],dp[k][i-(1<<j)]+dis[k][j]);
dp[j][i]=min(dp[j][i],dp[k][i]+dis[k][j]);
注意判一下j是否在集合i中
代码
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<stack> #include<vector> #include<algorithm> //#include<cmath> using namespace std; const int INF = 9999999; #define LL long long inline int read(){ int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } int N,M; int dp[17][131073]; int dis[18][18]; int main(){ N=read(); for(int i=0;i<=N;i++){ for(int j=0;j<=N;j++) dis[i][j]=read(); } for(int k=0;k<=N;k++)//FLOYD先跑一遍 for(int i=0;i<=N;i++) for(int j=0;j<=N;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); memset(dp,INF,sizeof(dp)); dp[0][0]=0; for(int i=0;i<(1<<(N+1));i++){//因为我们最后要回点0,所以要N+1 for(int j=0;j<=N;j++) for(int k=0;k<=N;k++){ if((i|(1<<j))!=i){//判一下正确性,点j是否在集合i中 continue; } dp[j][i]=min(dp[j][i],dp[k][i-(1<<j)]+dis[k][j]); dp[j][i]=min(dp[j][i],dp[k][i]+dis[k][j]); } } printf("%d ",dp[0][(1<<(N+1))-1]); return 0; }
hoj2662经典状压dp//myfirst状压dp
题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=26621.引言:用dp解决一个问题的时候很重要的一环就是状态的表示,一般来说,一个数组即可保存状态。但是有这样的一类题目,它们具有dp问题的特性,但状态中所包含的信息过多,... 查看详情
动态规划---状压dp2(代码片段)
今天模拟,状压dp又没写出来。。。还是不会啊,所以今天搞一下这个状压dp。这里有一道状压dp的板子题:CornFields就是一道很简单的状压裸题,但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结:上题干... 查看详情
状压dp(代码片段)
这几天都在学习状压DP,总结一下,首先是状压DP的工具。类型符号规则例子按位与&同1为1,其余为09 00001001&5 000001011 &nb 查看详情
foreignnumber[状压dp]
...leInput 123455SampleOutput 24HINT Solution 我们运用状压DP,令f[j][opt]表示当前余数为j,状态为opt的方案。 状态记录的是:各个数字被用了几次。 那么我们就可以状压了。先 查看详情
第一次接触状压dp(代码片段)
状压DP入门及理解*(另类的暴力)* 一般状态数不多的时候就会开数组,但是有的状态并不好表示,于是,状压DP就产生了。 状压DP应该是分两类的,一类是压缩状态,另一类是舍弃状态。 &... 查看详情
算法复习——状压dp
状压dp的核心在于,当我们不能通过表现单一的对象的状态来达到dp的最优子结构和无后效性原则时,我们可能保存多个元素的有关信息··这时候利用2进制的01来表示每个元素相关状态并将其压缩成2进制数就可以达到目的····... 查看详情
fzu2188状压dp
G-SimpleStringProblemTimeLimit:2000MS MemoryLimit:32768KB 64bitIOFormat:%I64d&%I64uSubmitStatusPracticeFZU2218DescriptionRecently,youhavefoundyourinte 查看详情
dp-状压dp(代码片段)
...w.bilibili.com/video/BV1Z4411x7Kw?from=search&seid=13855865082722302053状压介绍:状态表示: 转移方程:i是当前节点,j是下一步要走的节点 子集枚举:核心代码:1。由当前枚举未知首先枚举状态,枚举S中包含的节点:枚... 查看详情
d.romanandnumbers(状压dp)(代码片段)
D.RomanandNumbers(状压dp)把nnn的每一位状压,问题等价于选择一个顺序走完这cntcntcnt个位使得(modm)=0\\pmodm=0(modm)=0答案。令dp[i][j]dp[i][j]dp[i][j]表示状态iii模mmm余jjj的答案。转移时需要注意最高位对应的数不能为000。初始化... 查看详情
poj2411mondriaan'sdream(状压dp)
【POJ2411】Mondriaan‘sDream(状压dp)TimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:14107 Accepted:8152DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,aft 查看详情
simplestringproblem(状压dp)(代码片段)
SimpleStringProblemRecently,youhavefoundyourinterestinstringtheory.Hereisaninterestingquestionaboutstrings.YouaregivenastringSoflengthnconsistingofthefirstklowercaseletters.Youarerequiredtofindtwonon- 查看详情
状压dp初探·总结
...最优还是最优,无后还是无后,所以它比较好理解。 状压,顾名思义就是要将一些状压想办法压缩起来(可以压,也可以删)。其中这些状态都满足相似性和数量很多。这样才好压而且压得有意义。常见于一般的方格题,网 查看详情
各种dp分类整理
各种dp分类整理数位dp因为比较重要,单独写一篇见这篇状压dp某篇学术垃圾中指出,我们可以说,所有的dp都会有一个“状压”。只不过普通的dp压缩的比较浅显,而使用二进制的状压dp压的比较复杂,才叫它“状压dp”所以这里... 查看详情
b.littleponyandharmonychest(状压dp)(代码片段)
B.LittlePonyandHarmonyChest(状压dp)考虑bi≥59b_i\\ge59bi≥59时,bi=1b_i=1bi=1更优。所以只需考虑bi≤59b_i\\le59bi≤59。又因为bbb数组两两互质。即每个质因子只能被一个数使用。且≤59\\le59≤59的质因子只有161616个。考虑... 查看详情
poj2441状压dp
ArrangetheBullsTimeLimit: 4000MS MemoryLimit: 65536KTotalSubmissions: 5289 Accepted: 2033DescriptionFarmerJohnson‘sBullsloveplayingbasketballverymuch.Butnoneofthemw 查看详情
poj2411状压dp经典
Mondriaan‘sDreamTimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:16771 Accepted:9683DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthed 查看详情
zoj3471mostpowerful(状压dp)
Recently,researchersonMarshavediscoveredNpowerfulatoms.Allofthemaredifferent.Theseatomshavesomeproperties.Whentwooftheseatomscollide,oneofthemdisappearsandalotofpowerisproduced.Researchersknowthewayev 查看详情
jzoj3747(状压dp)
这题是一道状压DP,暂时还不是很懂.#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;constintLENM=1010,N=11,M=1e9+7;chars[N];intn,m,u,ind[200],f[LENM][1<<10],g[N],ans[N],gg[N 查看详情