[JZOJ4648] 【NOIP2016提高A组模拟7.17】锦标赛

野性酷女 2021-09-29 13:16 338阅读 0赞

# 题目 #

> ## 描述 ##
> 
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ExODQ3MjI1ODg5_size_16_color_FFFFFF_t_70]

## 题目大意 ##

有nnn个人，你要确定一个出场序列。每次新上台的人就会和擂主打一架，胜利的人继续当擂主。题目给出两两之间打架胜利（失败）的概率。  
问111选手坚持到最后的最大概率。

--------------------

# 思考历程 #

看这数据范围这么小，立即想到状压DP！  
自然而然地想到状态：设fs,if\_\{s,i\}fs,i表示上了台的人的状态为sss，当前擂主为iii的最大概率。  
于是我很快就发现了这个方法的bug。每次转移都会有输或硬两种状态，但万一它们以后要合并到一起呢？  
假设状态AAA转移到状态BBB和CCC，接下来状态BBB和CCC又要转移到DDD。按理来说，从AAA到DDD的这两个不同状态是可以合并的，但怎么合并呢？  
没有办法合并啊！它们会被看做是不同的状态，然后取个maxmaxmax。  
所以我就迷茫了，不知道该怎么做。  
开始往什么贪心。结论题方面想……

--------------------

# 正解 #

实际上这题的正解就是状压DP。  
我很震惊，难道我找出来的这个东西对答案没有任何影响？  
哼，一定是数据错了  
然后我就发现了区别：反着和正着的区别。  
我一开始并不理解。反着推和正着推有什么不一样吗？状态之间的转移都是一个有向无环图啊！  
后来看看题解才发现了本质上的区别：正着推时，每个状态都会被分裂为许多个状态，有些状态在后面还需要合并，有些就不用，这样就很难处理；反着推时，由于我们已经预知了未来，我们只需要从后往前合并状态，并没有什么分裂状态的鬼玩意儿。这样我们就不用想之前的那些情况了。

然后还有另一种神方法，由LYL发明的O(n2)O(n^2)O(n2)贪心做法。  
我们思考一下111号选手放在哪里最优。  
111号选手要和排在它后面的选手决斗一次，并且必须要胜利，所以概率为这些选手的胜率之积。  
胜率总是不超过111的，所以越乘越小。所以将111放在最后面是最优的。  
接着我们就用和DP做法一样的思路，从后往前推。设个fif\_ifi表示这一个为iii时的最大概率，方程式一样的。  
我们贪心地选择其中最大的那个。  
接下来就将这个当做新的111号，重复这样的过程。  
%%%LYL

--------------------

# 代码 #

状压DP

using namespace std;
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    inline void update(double &a,double b){ a<b?a=b:0;}
    int n;
    double a[18][18];
    double f[1<<18][18];
    int main(){ 
    	scanf("%d",&n);
    	for (int i=0;i<n;++i)
    		for (int j=0;j<n;++j)
    			scanf("%lf",&a[i][j]);
    	f[(1<<n)-1][0]=1;
    	for (int i=(1<<n)-2;i>=0;--i)
    		for (int j=0;j<n;++j)
    			if (i>>j&1)
    				for (int k=0;k<n;++k)
    					if (!(i>>k&1))
    						update(f[i][j],f[i|1<<k][j]*a[j][k]+f[i|1<<k][k]*a[k][j]);
    	double ans=0;
    	for (int i=0;i<n;++i)
    		update(ans,f[1<<i][i]);
    	printf("%.7lf\n",ans);
    	return 0;
    }

LYL神贪心

using namespace std;
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define N 5010
    int n;
    double a[N][N];
    int q[N];
    bool vis[N];
    double f[N];
    int main(){ 
    	scanf("%d",&n);
    	for (int i=1;i<=n;++i)
    		for (int j=1;j<=n;++j)
    			scanf("%lf",&a[i][j]);
    	vis[q[0]=1]=1;
    	f[0]=-1,f[1]=1;
    	for (int i=1;i<n;++i){ 
    		int mx=0;
    		for (int j=1;j<=n;++j)
    			if (!vis[j]){ 
    				f[j]=f[j]*a[j][q[i-1]]+f[q[i-1]]*a[q[i-1]][j];
    				if (f[j]>f[mx])
    					mx=j;
    			}
    		vis[q[i]=mx]=1;
    	}
    	printf("%.7lf\n",f[q[n-1]]);
    	return 0;
    }

# 总结 #

有时候正着推和反着推真的很不一样……

转载于:https://www.cnblogs.com/jz-597/p/11145221.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ExODQ3MjI1ODg5_size_16_color_FFFFFF_t_70]: /images/20210725/73211a950af64e258a95654c9af07480.png