Codeforces 678E 状压DP

时间:2022-09-17 00:13:39

题意:有n位选手,已知n位选手之间两两获胜的概率,问主角(第一个选手)最终站在擂台上的概率是多少?

思路:一看数据范围肯定是状压DP,不过虽然是概率DP,但是需要倒着推;我们如果正着推式子的话,初始状态是不确定的,因为并不知道一开始把哪个人放在擂台上最后主角获胜的概率最大。所以我们可以假设主角最后获胜的概率是1,然后倒着推。设dp[i][j]表示现在站在擂台上的是i号选手,状态是j,主角获胜的最大概率,其中状态j的k位置是1代表第k - 1个选手还没有被淘汰。所以dp[i][j] = max(dp[i][j ^ (1 << k)] * a[i][k] + dp[k][j * (1 << i)] * a[k][i]).代表的决策是:现在站在擂台上的人是i,如果k去挑战有2种情况:1,k获胜了,那么转移到dp[k][j * (1 << i)], 转移概率是a[k][j],k失败了同理。那么在当前状态选择k去挑战擂台的获胜的总概率是两种可能获胜概率的总和。

代码:

#include <bits/stdc++.h>
#define db double
using namespace std;
const int maxn = 100010;
db dp[18][1 << 18];
db a[18][18];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%lf", &a[i][j]);
dp[0][1] = 1;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if((i >> j) & 1) {
for (int k = 0; k < n; k++) {
if(k == j) continue;
if((i >> k) & 1) {
dp[j][i] = max(dp[j][i], dp[k][i ^ (1 << j)] * a[k][j] + dp[j][i ^ (1 << k)] * a[j][k]);
}
}
}
}
}
db ans = 0;
for (int i = 0; i < n; i++)
ans = max(ans, dp[i][(1 << n) - 1]);
printf("%.7lf\n", ans);
}

  

Codeforces 678E 状压DP的更多相关文章

  1. Codeforces 8C 状压DP

    题意:有个人想收拾行李,而n个物品散落在房间的各个角落里(n < 24).现在给你旅行箱的坐标(人初始在旅行箱处),以及n个物品的坐标,你一次只能拿最多两个物品,并且拿了物品就必须放回旅行箱,不 ...

  2. Codeforces 1215E 状压DP

    题意:给你一个序列,你可以交换序列中的相邻的两个元素,问最少需要交换多少次可以让这个序列变成若干个极大的颜色相同的子段. 思路:由于题目中的颜色种类很少,考虑状压DP.设dp[mask]为把mask为 ...

  3. CodeForces 11D&lpar;状压DP 求图中环的个数&rpar;

    Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no re ...

  4. codeforces 1185G1 状压dp

    codeforces 1185G1. Playlist for Polycarp (easy version)(动态规划) 传送门:https://codeforces.com/contest/118 ...

  5. Codeforces 1155F 状压DP

    题意:给你一张图,问最少保留多少条边,使得这张图是边双联通分量. 思路:如果一个点集中的点已经是边双联通分量,那么从这个点集中的点x出发,经过若干个不是点集中的点,回到点集中的点y(x可能等于y),那 ...

  6. Codeforces - 71E 状压DP

    参考官方题解 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rr ...

  7. codeforces Diagrams &amp&semi; Tableaux1 (状压DP)

    http://codeforces.com/gym/100405 D题 题在pdf里 codeforces.com/gym/100405/attachments/download/2331/20132 ...

  8. Codeforces Gym 100015F Fighting for Triangles 状压DP

    Fighting for Triangles 题目连接: http://codeforces.com/gym/100015/attachments Description Andy and Ralph ...

  9. Codeforces Gym 100610 Problem K&period; Kitchen Robot 状压DP

    Problem K. Kitchen Robot Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/10061 ...

随机推荐

  1. POJ 2718 Smallest Difference【DFS】

    题意: 就是说给你一些数,然后要求你使用这些数字组成2个数,然后求他们的差值最小. 思路: 我用的双重DFS做的,速度还比较快,其中有一个很重要的剪枝,若当前搜索的第二个数后面全部补零与第一个数所产生 ...

  2. CF723D&period; Lakes in Berland&lbrack;DFS floodfill&rsqb;

    D. Lakes in Berland time limit per test 2 seconds memory limit per test 256 megabytes input standard ...

  3. IT公司100题-3-求数组的最大子序列的和

    问题描述: 输入一个整形数组,数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和. 求所有子数组的和的最大值.要求时间复杂度为O(n). 例如输入的数组为1, -2 ...

  4. winform —— 界面

    winform 界面简单介绍 窗体事件:理解为委托变量,指向哪个函数,就执行哪个函数.窗体:显示窗体的过程是一个通过模板造对象的过程.先走构造函数,构造函数中的InitializeComponent( ...

  5. struts1&colon;Struts配置文件初解

    struts-config.xml是Struts的核心文件.该文件可配置各种组件,包括,FormBeans,Actions,ActionMappings,全局转发GlobalForwards,数据源D ...

  6. vim下使用YouCompleteMe实现代码提示、补全以及跳转设置

    配置YouCompleteMe 1. 安装vundle vundle是一个管理vim插件的工具,使用vundle安装YouCompleteMe比较方便. 按照作者在https://github.com ...

  7. UiAutomator源码分析之UiAutomatorBridge框架

    上一篇文章<UIAutomator源码分析之启动和运行>我们描述了uitautomator从命令行运行到加载测试用例运行测试的整个流程,过程中我们也描述了UiAutomatorBridge ...

  8. PHP的ip2long和long2ip函数的实现原理

    最近要做个十进制数字的可逆转换做邀请码,一直没搞清楚怎么弄的,实在太复杂了,今天弄IP时想到这个可以进行转换,于是研究了下原理: 主要是自己整理了下: $ip = '12.34.56.78'; $ip ...

  9. 转:Validation of viewstate MAC failed异常的原因及解决方法

    ViewState是一种机制,ASP.NET 使用这种机制来跟踪服务器控件状态值,否则这些值将不作为 HTTP 窗体的一部分而回传.也就是说在页面刷新或者回传的时候控件的值将被清空,我们在aspx.c ...

  10. 从零开始构建一个的asp&period;net Core 项目(二)

    接着上一篇博客继续进行.上一篇博客只是显示了简单的MVC视图页,这篇博客接着进行,连接上数据库,进行简单的CRUD. 首先我在Controllers文件夹点击右键,添加->控制器 弹出的对话框中 ...