二分查找算法:
二分查找算法就是从单调有序的集合中从两端不断查找元素,然后不断缩小范围直至查到该元素或缩至最小无解的过程。
时间复杂度:O (logn),优于直接顺序查找O(n)
例:

   //x:待查找的元素, n:数组集合大小, num数组单调递增
    int low=0,high=n,mid,res = -1;  //low:集合下界 high:集合上节
    while(low<=high)                     
    {
        mid=(low+high)/2;   //mid:将集合分割为两部分
        if(num[mid]==x)	 //查找到符合元素x
        {
           res = mid;
	   break;	           
        }        
        else if(num[mid]<x)//x在右边部分,调整集合下界
           low=mid+1;
        else		     //x在左边部分,调整集合上界
           high=mid-1;
    }                     //若未找到x,则res = -1

三分法:
当需要求某凸性或凹形函数的极值,通过函数本身表达式并不容易求解时,就可以用三分法不断逼近求解。
例:

类似二分的定义Left和Right
mid = (Left + Right) / 2
midmid = (mid + Right) / 2;
如果mid靠近极值点,则Right = midmid;
否则(即midmid靠近极值点),则Left = mid;

double mid, midmid;
while ( low + eps < high )
{
    mid = (low + high) / 2;
    midmid = (mid + high ) / 2;
    double cmid = cal(mid);
    double cmidmid = cal(midmid);
    if ( cmid > cmidmid ) 
		    high = midmid;
    else 
        low = mid;
}
double cal(double x)
{
    returnD* (h - x) / (H - x) + x;
    //这里放要求的函数;    
}

在实际问题中,有时利用二分、三分法可以较为精确地求解出一些临界值。

DP:
DP的种类有很多:经典DP,区间DP,树形DP,数位DP,概率(期望)DP,状压DP,数据结构优化的DP等。动态规划真的是很多,是难点。这大概也是比赛时很多同学卡住的原因吧,老师说DP没什么好办法,多做题呗。现在的题目很多就感觉很不简单了,以后还有这么多,感觉压力好大。还是要多看资料,多做题啊。

状压DP是基于状态压缩的动态规划,又叫做集合动态规划。
这是一类以集合为状态的特殊的动态规划问题。有些时候,需要被记录到得状态有很多,但是对每个状态都开一维来记录显然是行不通的,我们就考虑把这些状态压缩一下,通常情况下,若只有两种状态,我们会把状态用二进制表示,每个格子的状态只有1或0,然后把它转成十进制来记录。