哪些网站是中文域名,如何用织梦做网站详细教程,天津和平做网站公司,深圳seo推广【noip模拟赛4】Matrix67的派对描述 Matrix67发现身高接近的人似乎更合得来。Matrix67举办的派对共有N(1N10)个人参加#xff0c;Matrix67需要把他们安排在圆桌上。Matrix67的安排原则是#xff0c;圆桌上任意两个相邻人的身高之差不能超过K。请告诉Matrix67他共有多… 【noip模拟赛4】Matrix67的派对 描述 Matrix67发现身高接近的人似乎更合得来。Matrix67举办的派对共有N(1N10)个人参加Matrix67需要把他们安排在圆桌上。Matrix67的安排原则是圆桌上任意两个相邻人的身高之差不能超过K。请告诉Matrix67他共有多少种安排方法。 输入 第一行输入两个用空格隔开的数N和K其中1N101K1 000 000。 第二行到第N1行每行输入一个人的身高值。所有人的身高都是不超过1 000 000的正整数 输出 输出符合要求的安排总数 输入样例 1 4 10
2
16
6
10 输出样例 1 2做法用dfs试每一条路记录一个步数step当stepn切该点和起点差距小于k时答案就累计一个。开3个数组1 pre 记录 step-1 时是哪个点用来与step时的各个数比较判断能否做一起。2 flag 在试没一条路时用flag标记每一条路防止死循环这条路探完后重置为0。3 high 记录每个人的高。注意有特解 当n1时ans 应为1。 #includeiostream
#includecmath
#includestdio.h
#includevector
#includestring.h
#includemath.h
#includealgorithm
using namespace std;
const int maxn11;
int high[maxn],pre[maxn];
int n,k,ans;
bool flag[maxn];void dfs(int step)
{for(int i2;in;i){if(!flag[i]abs(high[i]-high[pre[step-1]])k){flag[i]1;pre[step]i;if(stepnabs(high[pre[step]]-high[1])k){ans;}elsedfs(step1);flag[i]0;}}
}int main(void)
{// freopen(input.txt,r,stdin);cinnk;for(int i1;in;i){cinhigh[i];}if(n1)ans1;else{ans0;flag[1]1;pre[1]1;dfs(2);}coutansendl;return 0;
} 转载于:https://www.cnblogs.com/zgncbsylm/p/10579988.html
