Robert Anderson's Blog

http://www.cs.nctu.edu.tw/~huanpo/0519.ppt

来看一下ST算法是怎么实现的(以最大值为例）：
　　首先是预处理，用一个DP解决。设a是要求区间最值的数列，f表示从第i个数起连续2^j个数
中的最大值。例如数列3 2 4 5 6 8 1 2 9 7
,f[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。
f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……从这里可以看出f其实就等于a。这样，Dp的状态、初值都已经有了，剩下的
就是状态转移方程。我们把f平均分成两段（因为f一定是偶数个数字），从i到i+2^(j-1)-1为一段，i+2^(j-1)到i+2^j-1为一段
(长度都为2^（j-1）)。用上例说明，当i=1，j=3时就是3,2,4,5 和
6,8,1,2这两段。f就是这两段的最大值中的最大值。于是我们得到了动规方程F=max（F,F）.
　　接下来是得出最值，也许你想不到计算出f有什么用处，一般毛想想计算max还是要
O(logn)，甚至O(n)。但有一个很好的办法，做到了O（1）。还是分开来。如在上例中我们要求区间[2，8]的最大值，就要把它分成[2,5]和
[5,8]两个区间，因为这两个区间的最大值我们可以直接由f[2，2]和f[5，2]得到。扩展到一般情况，就是把区间[l，r]分成两个长度为2^n
的区间（保证有f对应）。直接给出表达式：
　　k:=ln(l(r-l+1)/ln(2));
　　ans:=max(F[l，k],F[r-2^k+1,k]);
　　这样就计算了从i开始，长度为2^t次的区间和从r-2^i+1开始长度为2^t的区间的最大值（表达式比较烦琐，细节问题如加1减1需要仔细考虑

Idea #1: Heuristic Pruning
The easiest and most common use for heuristic functions is to prune
the search space. Assume the problem is to find the solution with the
minimum total cost. With an admissible heuristic function, if the cost
of the current solution thus far is A, and the heuristic function returns
B, then the best possible solution which is a child of the current
solution is A+B. If the a solution has been found with cost C, where C
< A+B, there is no reason to continue searching for a solution from
this state.

原本是想貼之前拿到的講義
不過我實在有點看不太懂裡面在寫啥阿(查)
它寫什麼展開樹 一開始我還想說那是啥
結果應該是生成樹(Spanning Tree)

卡車說的沒錯
是很簡單的XD
而且發現真的跟SPFA幾乎一樣吧
 

假設已經知道起點和終點
而每個情況最大拓展的STATE數量是原本的R倍
則F(n) = R * F(n - 1) where F(0) = 1
那個走N步就可能會產生R^N種情形

我想會很有用
就學起來吧
接下來比賽就盡我所能了
 

轉貼我自己 2008.6.27的文章

這次又更快了，這是從大陸那邊找來的，後來終於想通他們的原理了
他們用的是位元運算，非常快，而我將他們程式碼改了些，因為他們行跟列與我們相反
而且他們所謂的對稱性，似乎無法紀錄解答，這支程式原本也只能算出有幾組解答，目前這支基本程式是紀錄目前解答狀況，若需要記錄解答則另外建立陣列，否則刪除那段就行了
利用這些程式碼，個人成功解答了Another N Queen
#include <cstdlib>
#include <cstdio>
#define MAX 16

long sum = 0, upperlim = 1;    
long now[MAX];

int test(long, long, long, int);

int main(int argc, char *argv[])
{
   int n = 16;

   scanf("%d", &n);

   upperlim = (upperlim << n) - 1;        

   test(0, 0, 0, 0);
   printf("CASE %d: %ld combinations.\n", n, sum);
  
   system("PAUSE");
   return 0;
}

int test(long col, long ld, long rd, int row)
{
   if (col != upperlim)
   {
     long pos = upperlim & ~(col | ld | rd);
     while (pos)
     {
        long p = pos & -pos;                                             

        pos -= p;                          
       
        now[row]=p;
       
        test(col + p, (ld + p) << 1, (rd + p) >> 1, row+1);                             
       }
   }
   else  
   {
  
       sum++;
   }
}

轉貼我自己2008 8/6的文章
 
今天自己寫了一次N皇后的回溯程式，結果發現位元運算有些地方並不如我想像一般，所以今天把所有地方重新做一次整理，其中包括我之前就知道的
關於!與~
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    int a=1;
    
    printf("%d %d\n", !a, ~a);
    
    system("PAUSE");
    
    return EXIT_SUCCESS;
}
本段程式碼輸出結果: 0 -2
下列以1Byte舉例
因為00000001
每位數取相反為11111110，正好為二的捕數法的-2
而!呢，只是取Boolean值的相反，跟位元運算無關
改成這樣
a=5;
   
printf("%d %d\n", !a, ~a);
將會輸出0 -6，即可證明
另外 || 、 | 與 &&、&之間的關係類似
|、&是針對每一個數字位元去做運算，而||、&&皆是布林值運算
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    int a=3, b=2;
   
    printf("%d %d\n", a&&b, a||b);
       
   
    system("PAUSE");
   
    return EXIT_SUCCESS;
}
輸出結果 1 1
分解動作→3為true 2為true，則AND之後→true
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    int a=3, b=2;
   
    printf("%d %d\n", a&b, a|b);
       
   
    system("PAUSE");
   
    return EXIT_SUCCESS;
}
如果是這樣的話，輸出結果 2 3
看成二進位制的運算
11 & 10 = 10 ； 11 | 10 = 11