博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[USACO08NOV]奶牛混合起来Mixed Up Cows
阅读量:5281 次
发布时间:2019-06-14

本文共 2539 字,大约阅读时间需要 8 分钟。

题目描述

Each of Farmer John's N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck.

Gangsta cows are rebellious and line up to be milked in an order called 'Mixed Up'. A cow order is 'Mixed Up' if the sequence of serial numbers formed by their milking line is such that the serial numbers of every pair of consecutive cows in line differs by more than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a 'Mixed Up' lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5 and 6 differ by 1).

How many different ways can N cows be Mixed Up?

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

POINTS: 200

约翰家有N头奶牛,第i头奶牛的编号是Si,每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气,为表达不满的情绪,她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中,相邻奶牛的编号之差均超过K。比如当K = 1时,1, 3, 5, 2, 6, 4就是一支混乱的队伍, 而1, 3, 6, 5, 2, 4不是,因为6和5只差1。请数一数,有多少种队形是混乱的呢?

输入格式

* Line 1: Two space-separated integers: N and K

* Lines 2..N+1: Line i+1 contains a single integer that is the serial number of cow i: S_i

输出格式

* Line 1: A single integer that is the number of ways that N cows can be 'Mixed Up'. The answer is guaranteed to fit in a 64 bit integer.

输入输出样例

输入 #1
4 1 3 4 2 1
输出 #1
2

说明/提示

The 2 possible Mixed Up arrangements are:

3 1 4 2

2 4 1 3

 

【解题思路】

N (4 <= N <= 16),定义状态值state(范围:0-216-1),表示当前含哪几头牛,如表:

牛 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

位序 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

取值 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1

含义 第i位取值为1/0,表示含/不含第(i+1)头牛

举例 49=0000 0000 0001 1001,表示含第1、4、5头牛

N头牛的身上的编号 s[1],s[2],…,s[N]

dp[last][state]表示最后一头牛为last,当前含牛的状态为state,共有多少组符合条件的队伍。

dp[2][2],2=00…0010(二进制仅表示第2头牛的第1位为1) 该状态表示仅含第2头牛,

所以:dp[2][2]表示最后一头牛是2,仅含第2头牛,混乱队伍数量

dp[2][5],5=00…001001(二进制仅表示含第1、4头牛),这种情况不存在,dp[2][5]=0

初始情况,仅含1头牛,那么这头牛就是结尾

假设共含8头牛,下标列出各种初始情况

哪头牛

(last) 状态值

(二进制) 状态值

(十进制) 表示方法 参数含义 dp(last,state)

1 0000 0001 1 20 1<<0 若仅含第last头牛,则其状态state为1左移last-1位,或2的last-1次方 1

表示在仅有1头牛的情况下,属混乱状态。

【code】

1 #include 
2 #include
3 using namespace std; 4 int a[17],n,k1; 5 long long dp[16][1<<16],ans=0; 6 int main() 7 { 8 scanf("%d%d",&n,&k1); 9 for(int i=0;i
k1)18 dp[k][i|(1<
<

 

转载于:https://www.cnblogs.com/66dzb/p/11259072.html

你可能感兴趣的文章
文本分类资源和程序开源共享
查看>>
java进阶01 异常处理
查看>>
Django模板层学习笔记
查看>>
开源webos--云DWOS
查看>>
JAVA学习路线图(一文详解)
查看>>
.Net和C#的理解
查看>>
initramfs文件系统
查看>>
jffs2和yaffs2文件系统
查看>>
How to check Logstash's pulse
查看>>
python闭包
查看>>
Leetcode-Letter Combinations of a Phone Number
查看>>
IntelliJ Idea 2017 免费激活方法
查看>>
IOS8 App开发快速入门视频教程与案例分享 20课 附讲义
查看>>
40、mysql的历史简介
查看>>
【java】为什么阿里巴巴禁止在 foreach 循环里进行元素的 remove/add 操作
查看>>
boost相关函数
查看>>
iOS 设置导航栏之二(设置导航栏的颜色、文字的颜色、左边按钮的文字及颜色)...
查看>>
Java Bean 使用包装类型 还是基本类型
查看>>
常见同花顺面试题实例总结
查看>>
JQuery Offset实验与应用(转载)
查看>>