CF258D Little Elephant and Broken Sorting （带技巧的DP）

题面

$ solution: $

这道题主要难在考场上能否想到这个思路（即如何设置状态）（像我这样的蒟蒻就想不到呀QAQ）不过这一题确实很神奇！

$ f[i][j]: $ 表示第 $ a_i $ 个数比第 $ a_j $ 个数大的几率，这样设置状态比较好转移：对于每一次 $ a_i $ 与 $ a_j $ 的交换，他只会影响到序列里，每一个数与 $ a_i $ ， $ a_j $ 的胜率（一共有 $ n $ 次交换，只要每次交换复杂度在 $ O(n) $ 级别这道题就解决了了）。而且我们不难发现转移时每一个数与 $ a_i $ ， $ a_j $ 胜率的修改是 $ O(1) $ 的：

$ f[i][j]=(f[i][j]+f[j][i])\times 0.5 $
$ f[j][i]=(f[i][j]+f[j][i])\times 0.5 $

所以把数列中每一位修改后复杂度刚好为 $ O(n) $ 级别，满足要求！

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

using namespace std;

int n,m;

int a[1001];

db ans,f[1001][1001];

inline int qr(){

	char ch;

	while((ch=getchar())<'0'||ch>'9');

	int res=ch^48;

	while((ch=getchar())>='0'&&ch<='9')

		res=res*10+(ch^48);

	return res;

}

int main(){

	//freopen("inversion.in","r",stdin);

	//freopen("inversion.out","w",stdout);

	n=qr(),m=qr();

	for(rg i=1;i<=n;++i)a[i]=qr();

	for(rg i=1;i<=n;++i)

		for(rg j=i+1;j<=n;++j){

			if(a[i]>a[j])f[i][j]=1;

			if(a[j]>a[i])f[j][i]=1;

		}

	for(rg k=1,i,j;k<=m;++k){

		i=qr(),j=qr();

		for(rg k=1;k<=n;++k){

			if(i!=k&&j!=k){

				f[k][i]=f[k][j]=(f[k][i]+f[k][j])*0.5;

				f[i][k]=f[j][k]=(f[j][k]+f[i][k])*0.5;

			}

		}f[i][j]=f[j][i]=(f[i][j]+f[j][i])*0.5;

	}

	for(rg i=1;i<=n;++i)

		for(rg j=i+1;j<=n;++j)

			ans+=f[i][j];

	printf("%.8lf",ans);

	return 0;

}

巴特西

CF258D Little Elephant and Broken Sorting （带技巧的DP）

题面

$ solution: $

$ code: $

最新文章

热门文章