[状压DP]邦德I

2024-01-30 06:32

文章标签 dp 状压邦德

本文主要是介绍[状压DP]邦德I，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

每个人都知道詹姆斯邦德，著名的007，但很少有人知道很多任务都不是他亲自完成的，而是由他的堂弟们吉米邦德完成（他有很多堂弟），詹姆斯已经厌倦了把一个个任务分配给一个个吉米，他向你求助。
每个月，詹姆斯都会收到一些任务，根据他以前执行任务的经验，他计算出了每个吉米完成每个任务的成功率，要求每个任务必须分配给不同的人去完成，每个人只能完成一个任务。
请你编写程序找到一个分配方案使得所有任务都成功完成的概率。

Input

输入第一行包含一个整数N,表示吉米邦德的数量以及任务的数量（正好相等,1<=N<=20）。
接下来N行，每行包含N个0到100之间整数，第i行的第j个数Aij表示吉米邦德i完成任务j成功的概率为Aij%

Output

输出所有任务成功完成最大的概率，结果保留6位小数。

Sample Input

输入1：
2
100 100
50 50

输入2：
2
0 50
50 0

输入3：
3
25 60 100
13 0 50
12 70 90

Sample Output

输出1：
50.000000

输出2：
25.000000

输出3：
9.100000

分析

赛时用贪心水的分
显然是DP（因为最优化）
而且我们发现如果将所有状态放进数组，显然会MLE
考虑状压DP
先设fi为n个吉米分别做哪个任务的最大概率
显然这是个二十进制，不能采用（20^2）
那么我们考虑缩减
设fi为n个吉米中用1表示接了任务，0表示没接任务的最大概率，二进制（2^20）
可以接受，所以考虑动态转移方程
易得：
fi=max{fi-2^j *aj,i中为1的总数（有多少个1，这次就是在做第多少个任务嘛）
自行理解一下

#include <iostream>
#include <cstdio>
#define rep(i,a,b) for (i=a;i<=b;i++)
using namespace std;
double a[21][21];
int b[22],c[21];
double f[2097152];
int n,i,j;
int m;
int main()
{scanf("%d",&n);rep(i,1,n)rep(j,1,n){scanf("%lf",&a[i][j]);a[i][j]/=100;}f[0]=100;b[1]=1;rep(i,2,n+1)b[i]=b[i-1]*2;rep(i,1,b[n+1]-1){m=0;rep(j,1,n)if (i&b[j]){m++;c[m]=j;}rep(j,1,m)f[i]=max(f[i],f[i-b[c[j]]]*a[c[j]][m]);}printf("%.6lf",f[b[n+1]-1]);
}