/ Vijos / 题库 /

萌萌的哈密顿

萌萌的哈密顿

背景

萌萌还很小,绵羊爸爸却开始给她介绍哈密顿回路了。但是萌萌实在太小了,她还不能记住哈密顿回路的性质和许许多多的判断定理。

描述

这天,绵羊爸爸给了萌萌一个图形:一个正 N (4 ≤ N ≤ 50) 边形,将它的中心与各个顶点连线(对于给出的长度,不用考虑图形的正确性,比如绵羊爸爸可以把它放在黎曼平面上),要求萌萌从O点出发,计算出长度为L的哈密顿回路的个数。但是小萌萌并不很清楚哈密顿回路的概念,在她找到的路径中每个点(包括O点)以及每条边(共 2×N条边)都可能出现好几次或是一次都没有。小萌萌没有足够的耐心找出所有的路径,她需要你来告诉她她最多可能找到几条长度为L的不同路径。

格式

输入格式

输入的第一行,有2个正整数N,L (4 ≤ N ≤ 50; 1 ≤ L ≤ 600),分别表示正多边形边数和需要找的路径的长度。

第二行有 N 个不超过10的正整数,表示正多边形的边长。第1个数表示顶点1到顶点2的距离,第1个数表示顶点2到顶点3的距离,依此类推,第N个数表示顶点N到顶点1的距离。

第三行有N个不超过10的正整数,表示顶点与中心连线的长度。第i个数表示中心与第i个顶点的连线长度。

输出格式

输出文件仅一行,表示不同的路径数目。结果不超过200位。

样例1

样例输入1

4 2
1 1 1 1
1 1 1 1

样例输出1

4

限制

所有测试点时限均为1000ms

来源

2009年江中信奥模拟赛

信息

ID
1658
难度
7
分类
动态规划 | 环形DP高精度 点击显示
标签
(无)
递交数
330
已通过
73
通过率
22%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

2009年江中信奥模拟赛