Codeforces 385 D Bear and Floodlight - c++编程基础

TOP

Codeforces 385 D Bear and Floodlight

2015-07-20 17:35:03 来源: 作者: 【大中小】浏览:2次

题目链接~~>

做题感悟：比赛的时候最后有点蛋疼了，处理点的坐标处理晕了，so~比赛完清醒了一下就AC了。

解题思路：

状态压缩DP ,只有 20 个点，如果安排灯的时候只有顺序不同的问题，完全可以用状态压缩去递推出来，只是处理点的坐标的时候很麻烦，理清思路就好了。

状态方程： dp [ S | (1 << i ) ] = max( dp[ S |( 1 << i ) ] , dp[ S ] + W ) , 在状态 S 的情况下再添加 i 点（S 中先前不含 i 点），这样一直更新就 ok 了。

代码（有点挫了）：

#include
  
   
#include
   
     #include
     #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   using namespace std ; #define INT __int64 const double INF = 99999999 ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const int MY = 100000 + 5 ; const int MX = (1<<20) + 5 ; int n ; double st ,sd ,dp[MX] ,ans ; struct node { double x ,y ,z ; }Tx[100] ; double ct(double x ,int i) { double sx = Tx[i].x ,sy = Tx[i].y ; double sa = Tx[i].z ; // 角度 double dis = sqrt((sx-x)*(sx-x)+sy*sy) ; double a = sa*PI/(180*1.0) ,b ,L ,L1 ,c ; if(sx == x) // 如果在正上方 { if(a == PI/2.0) return ans ; else return sy * tan(a) ; } else if(x < sx) // 在右边 { double ex = acos(sy/dis) ; if(ex == a) // 正好 return L = dis*sin(a) ; else if(a < ex) // 小于 { b = asin(sy/dis) ; // 度数 L = dis*cos(b) ; a = a + b ; L = L - sy/tan(a) ; } else { c = acos(sy/dis) ; L1 = dis*sin(c) ; c = a - c ; L = L1 + sy*tan(c) ; } return L ; } else if(x > sx) { c = acos(sy/dis) ; if(c + a > PI/2.0) return ans ; else { a = a + c ; L = sy*tan(a) ; return L - dis*sin(c) ; } } } void DP() { for(int i = 0 ;i < (1<
                  
                   = sd-st) cout<
                   
                    >Tx[i].x>>Tx[i].y>>Tx[i].z ; DP() ; } return 0 ; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj - 1170 - Shopping Offers（..	下一篇：[leetcode]Populating Next Right..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: