The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

TC SRM 458 DIV ,500

位运算很重要啊,开始用递归数组生成状态,结果超时了,做了这道题才知道,原来位运算才是王道。
#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);


    }

}
;

posted on 2010-01-22 19:01 abilitytao 阅读(1083) 评论(1)  编辑 收藏 引用

评论

# re: TC SRM 458 DIV ,500 2010-01-24 14:07 罗莱家纺官方网

上的的积分看到发  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理