P2915 [USACO08NOV]奶牛混合起来Mixed Up Cows
2018-06-17 22:12:42来源:未知 阅读 ()
题目描述
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.
输入输出样例
4 1 3 4 2 1
2
说明
The 2 possible Mixed Up arrangements are:
3 1 4 2
2 4 1 3
变量名冲突调了好久,,,
状压dp。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #define lli long long int 7 using namespace std; 8 const int maxn=0x7ffffff; 9 int n,k1; 10 int a[17]; 11 long long dp[16][1<<16]; 12 int main() 13 { 14 scanf("%d%d",&n,&k1); 15 for(int i=0;i<n;i++) 16 scanf("%d",&a[i]); 17 for(int i=0;i<n;i++) 18 dp[i][1<<i]=1; 19 for(int i=0;i<(1<<n);i++) 20 for(int j=0;j<n;j++) 21 if(i & (1<<j)) 22 for(int k=0;k<n;k++) 23 if(!(i&(1<<k))&&abs(a[j]-a[k])>k1) 24 dp[k][i|(1<<k)]+=dp[j][i]; 25 long long ans=0; 26 for(int i=0;i<n;i++) 27 ans+=dp[i][(1<<n)-1]; 28 printf("%lld",ans); 29 return 0; 30 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 长乐培训Day3 2019-08-16
- 1405 奶牛的旅行 2018-06-17
- 3122 奶牛代理商 VIII 2018-06-17
- P2858 [USACO06FEB]奶牛零食Treats for the Cows 2018-06-17
- P1284 三角形牧场 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash