Marriage Ceremonies(状态压缩dp)
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Description
You work in a company which organizes marriages. Marriages are not that easy to be made, so, the job is quite hard for you.
The job gets more difficult when people come here and give their bio-data with their preference about opposite gender. Some give priorities to family background, some give priorities to education, etc.
Now your company is in a danger and you want to save your company from this financial crisis by arranging as much marriages as possible. So, you collect N bio-data of men and N bio-data of women. After analyzing quite a lot you calculated the priority index of each pair of men and women.
Finally you want to arrange N marriage ceremonies, such that the total priority index is maximized. Remember that each man should be paired with a woman and only monogamous families should be formed.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case contains an integer N (1 ≤ n ≤ 16), denoting the number of men or women. Each of the next N lines will contain N integers each. The jth integer in the ith line denotes the priority index between the ith man and jthwoman. All the integers will be positive and not greater than 10000.
Output
For each case, print the case number and the maximum possible priority index after all the marriages have been arranged.
Sample Input
2
2
1 5
2 1
3
1 2 3
6 5 4
8 1 2
Sample Output
Case 1: 7
Case 2: 16
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[][] ;
int dp[][ << ] ;
int n ; int main ()
{
// freopen ("a.txt" , "r" , stdin ) ;
int T ;
scanf ("%d" , &T ) ;
int ans = ;
while (T--) {
scanf ("%d" , &n ) ;
for (int i = ; i < n ; i++) {
for (int j = ; j < n ; j++) {
scanf ("%d" , &a[i][j]) ;
}
}
for (int i = ; i < n ; i++) {
for (int j = ; j < << n ; j++ ) {
dp[i][j] = - ;
}
}
for (int i = ; i < n ; i++) {
dp[][ << i] = a[][i] ;
}
for (int i = ; i < n ; i++) {
for (int j = ; j < << n ; j++) {
if (dp[i - ][j] != -) {
for (int k = ; k < n ; k++) {
if ( ! (j & << k) ) {
dp[i][j | << k] = max (dp[i][j | << k] , dp[i - ][j] + a[i][k] ) ;
}
}
}
}
}
printf ("Case %d: %d\n" , ++ans , dp[n - ][( << n) - ] ) ;
}
return ;
}
先把“ 数据 ”存入 下标为 1 << 0 , 1 << 1 , 1 << 2 , 1 << n - 1的这几个位置,然后就是一般的dp过程了
状态压缩dp我觉得有两点蛮神奇的(当然能用数学方法证明的)
:
1,! ( j & 1 << k ) 这能让已经加过的滚蛋;orz
2,(1 << 0) + (1 << 1 ) + ... + (1 << n - 1) = (1 << n ) - 1 orz 不仔细看还真没发觉
最新文章
- mvc url 伪静态
- Android SeekBar自定义使用图片和颜色显示
- POJ 1488
- ASP.NET设置404页面返回302HTTP状态码的解决方法
- python解释器内建函数002
- Linux下SVN安装配置全程实录(转)
- Fitnesse用系列三
- 吴恩达深度学习第2课第3周编程作业 的坑(Tensorflow+Tutorial)
- SSM-SpringMVC-25:SpringMVC异常顶级之自定义异常解析器
- 科学计算工具Numpy
- .NET CORE学习笔记系列(2)——依赖注入【3】依赖注入模式
- python-ironicclient使用
- Sprng4之JDBC--很原始的使用方法
- Java编程思想 学习笔记3
- oracle 11g禁用和强制direct path read
- android的USB MTP &;&; USB CDC/USBnet(ECM, NCM, ACM) &;&; USB gardget
- C#编程(三十四)----------数组作为参数
- es6 用generator进行异步方法同步
- POJ 3597 Polygon Division 多边形剖分
- Navicat Premium 连接Oracle 数据库
热门文章
- Node基础:域名解析DNS(ok)
- 设置 git/npm/bower/pip/gem镜像或代理
- 在C#中使用官方驱动操作MongoDB ---转载
- [设计模式] javascript 之 适配器模式
- jQuery基础之(三)jQuery功能函数前缀及与window.onload冲突
- Memcached——分布式缓存
- cursor:pointer的意思
- 利用HTML5的Video进行视频截图并保存到本地
- 【CodeForces 618B】Guess the Permutation
- SQL Server数据库还原:";因为数据库正在使用,所以无法获得对数据库的独占访问权";