位運(yùn)算很重要啊，開始用遞歸數(shù)組生成狀態(tài)，結(jié)果超時了，做了這道題才知道，原來位運(yùn)算才是王道。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;
int n;
int a[20];
bool cheack(vector<int>x,int T,int a[],int i,int j)
{
if(x[i]<x[j]&&a[i]==1&&a[j]==0&&(x[j]-x[i])<=2*T)
return true;
if(x[i]>x[j]&&a[i]==0&&a[j]==1&&(x[i]-x[j])<=2*T)
return true;
return false;
}
void get(int sum)
{
int i;
for(i=n-1;i>=0;i--)
{
if(sum&(1<<i))
a[i]=1;
else
a[i]=0;
}
}
class BouncingBalls
{
public:
double expectedBounces(vector <int> x, int T)
{
n=x.size();
int sum=(1<<(n))-1;
int i;
int j,k;
int cnt=0;
for(i=0;i<=sum;i++)
{
get(i);
for(j=0;j<=n-1;j++)
{
for(k=j+1;k<=n-1;k++)
{
if(cheack(x,T,a,j,k))
cnt++;
}
}
}
return (double)cnt/(sum+1);
}
};