jzxx1526混乱的奶牛
题目描述输入
Farmer John的N(4 <= N <= 16)头奶牛中的每一头都有一个唯一的编号S_i(1 <= S_i <= 25,000). 奶牛为她们的编号感到骄傲, 所以每一头奶牛都把她的编号刻在一个金牌上, 并且把金牌挂在她们宽大的脖子上. 奶牛们对在挤奶的时候被排成一支"混乱"的队伍非常反感. 如果一个队伍里任意两头相邻的奶牛的编号相差超过K (1 <= K <= 3400), 它就被称为是混乱的. 比如说，当N = 6, K = 1时,1, 3, 5, 2, 6, 4 就是一支"混乱"的队伍, 但是 1, 3, 6, 5, 2, 4 不是(因为5和6只 相差1). 那么, 有多少种能够使奶牛排成"混乱"的队伍的方案呢? 对于你前10次的提交, 你的程序会在一部分正式的测试数据上运行, 并且返回运行的结果.
- 第 1 行: 用空格隔开的两个整数N和K * 第 2…N+1 行: 第i+1行包含了一个用来表示第i头奶牛的编号的整数: S_i
- 第 1 行: 只有一个整数, 表示有多少种能够使奶牛排成"混乱"的队伍的方案. 答案保证是一个在64位范围内的整数.
4 1
3
4
2
1
样例输出
2
来源
USACO 2008 November Gold
【jzxx1526混乱的奶牛】传送门
满分代码：
program haha;
var
n,i,j,k,m,tot : longint;
f: array[0..70000,0..25] of int64;
a,d: array[1..20] of longint;
procedure swap(var x,y: longint);
var
t : longint;
begin
t:=x;
x:=y;
y:=t;
end;
{ swap }
procedure init;
begin
readln(n,m);
for i:=1 to n do
readln(a[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]=0 then exit(f[x,y]);
dp:=0;
for i:=1 to n do
if 1<<(i-1) and x<>0 then
if abs(a[y]-a[i])>m then
dp:=dp+dp(x-1<<(y-1),i);
f[x,y]:=dp;
exit(dp);
end;
procedure print;
var
ans : int64;
begin
fillchar(f,sizeof(f),130);
for i:=1 to n do
f[1<<(i-1),i]:=1;
ans:=0;
for i:=1 to n do
inc(ans,dp(1<推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量