程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 385 D Bear and Floodlight

Codeforces 385 D Bear and Floodlight

編輯:C++入門知識

Codeforces 385 D Bear and Floodlight


題目鏈接~~>

做題感悟:比賽的時候最後有點蛋疼了,處理點的坐標處理暈了,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 ;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved