优秀高端网站建设公司,wordpress 伪静态 效果,做58同城那样的网站,福州制作网站软件Description A国有n个城市#xff0c;编号为1到n#xff0c;任意两个城市之间有一条路。shlw闲得没事干想周游A国#xff0c;及从城市1出发#xff0c;经过且仅经过除城市1外的每个城市1次#xff08;城市1两次#xff09;#xff0c;最后回到城市1。由于shlw很傻#…Description A国有n个城市编号为1到n任意两个城市之间有一条路。shlw闲得没事干想周游A国及从城市1出发经过且仅经过除城市1外的每个城市1次城市1两次最后回到城市1。由于shlw很傻他只愿意走一定长度多了少了都不干现在他想知道一共有多少种方案可供选择。 Input 第一行为两个整数nl分别为城市数和路程总长。之后n行每行n个整数其中第i行第j列为Ai,j满足Ai,i0;Ai,jAj,i。 Output 输出共1行为总方案数。 Sample Input 3 60 1 31 0 2 3 2 0 Sample Output 2 Data Constraint 对于30%1n10对于另外30%1n14,1l30对于100%1n14,1Ai,j100,000,000,1l2,000,000,000悄悄告诉你数据的答案都很大反正直接输0是没分的但都在int范围内。为了降低题目难度Aij的种类数不会太多 题解 题目大意有n个城市问每个城市都走一遍路径长度刚好为L的方案数30%暴力乱搜就好了O(n!)60%n14状压dp设f[i][j][k]表示当前经过的点的状态为i现在在点j当前路径长为kO(2^n*n^2*30)听说加个map可以跑70分100%n14折半搜索可以过记前半段除了1与i长度为n1后半段为n2那么如果确定了i只要满足前半段与后半段经过的点不重复且路径总长为l就可以计算答案了具体来说就是就是枚举一个点i枚举前半段的所有情况用hash记下来,再枚举后半段的所有情况并在hash中找到与之对应的前半段统计进答案中就好了代码 1 #include cstdio2 #include iostream3 #include cstring4 #define mo 192608175 #define ll long long6 #define N 157 using namespace std;8 int n,m,l,a[N][N],f[mo],ans,i;9 ll g[mo];
10 ll calc(int x,int y,int k){ return x*32768000000000lly*2000000000llk; }
11 int gethash(int x,int y,int k)
12 {
13 ll rcalc(x,y,k);
14 for (ir%mo;g[i]g[i]!r;imo?i0:i);
15 return i;
16 }
17 void dfs1(int d,int x,int y,int k)
18 {
19 if (xkl) return;
20 if (dm)
21 {
22 int pgethash(x,y,k);
23 g[p]calc(x,y,k),f[p]; return;
24 }
25 for (int i1;in;i) if (!(yi1)) dfs1(d1,i,y|1i,ka[x][i]);
26 }
27 void dfs2(int d,int x,int y,int k)
28 {
29 if (xkl) return;
30 if (dm)
31 {
32 int pgethash(x,((~y)((1n)-1))|1|1x,l-k);
33 ansf[p]; return;
34 }
35 for (int i1;in;i) if (!(yi1)) dfs2(d1,i,y|1i,ka[x][i]);
36 }
37 int main()
38 {
39 scanf(%d%d,n,l);
40 for (int i0;in;i) for (int j0;jn;j) scanf(%d,a[i][j]);
41 mn/2,dfs1(0,0,1,0),mn-m,dfs2(0,0,1,0),printf(%d,ans);
42 } 转载于:https://www.cnblogs.com/Comfortable/p/10339544.html
