ZOJ2676 动态规划优化

这道题裸的 dp 方程应该可以写的出来，我记录的状态如下：

$dp[i][j]$ 表示以 $a_i$ 为第一个元素，$a_j$ 为第二个元素的斐波那契序列的最大长度，这样 $i \leq j$ 转移方程：

$$dp[i][j]=dp[j][k]+1$$

其中 $a_k=a_i+a_j$

从后向前扫描，每次更新 $dp$ 值后更新最大长度以及第一第二项，最后的答案直接根据第一第二项迭代即可

现在遇到的最大问题就是转移，裸的转移是 $O(n)$ 的，直接从前向后扫一遍，找到第一个符合条件的 k，这样总的复杂度是枚举加上扫描，是 $O(n^3)$ 的，明显对 $n$ 为 $3000$ 的数据来说太大了，不可取。

后来想到了二叉树，嗯，就是 map，在树中维护值为 x 的最前位置，这样直接通过在树中找 $a_i+a_j$ 的最前位置即可，后来想想也不对，复杂度是$O(n^2 \times logn)$ 的，对于 STL 的大常数不放心，算了一下 $3000^2 \times lg{3000}$ 差不多$10^8$ 数量级，会 TLE。又开始想转移能不能压缩。

最后想到 hash 的办法，因为转移无非就是在一个序列中找一个 $x$ 对应的最前位置，直接将 $x$ 进行 hash，对应的 hash 值的位置存放我们要的 $x$ 对应的最前位置即可。

hash 函数乱写的 - -

发现其实数据重复的概率不大，没有优化，直接用了。。。

这样可以在近似 $O(1)$ 的时间内找到我们要的值，转移加上枚举就是 $O(n^2)$ 的了

我的代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX = 100000;
const int mod = 100007;

struct hbox {
  int st;
  hbox* s;
} hash[MAX], *h[mod], *cur;
int cnt[mod], pos;

unsigned int BKDHash(int s) {
  unsigned int r = abs(s);
  return (r * r & 0x7FFFFFFF) % mod;
}

bool has(int s, int& pos) {
  int d = BKDHash(s);
  hbox* p = h[d];
  while (p) {
    if (s == p->st) {
      pos = p - hash;
      return true;
    }
    p = p->s;
  }
  return false;
}

void insert(int s, int v) {
  int d = BKDHash(s);
  hbox* p = h[d];
  while (p) {
    if (s == p->st) {
      cnt[p - hash] = v;
      return;
    }
    p = p->s;
  }
  cur->st = s;
  cur->s = h[d];
  h[d] = cur++;
  cnt[cur - hash - 1] = v;
}

void init() {
  memset(h, 0, sizeof(h));
  cur = hash;
}

int a[3100];
short dp[3100][3100];

int main() {
  int n;
  int x, y, pos;
  bool blocks = false;
  int ret;
  while (~scanf("%d", &n)) {
    if (blocks) {
      puts("");
    } else {
      blocks = true;
    }
    init();
    for (int i = 0; i < n; i++) {
      scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        dp[i][j] = 1;
      }
    }
    x = a[0];
    ret = 0;
    for (int j = n - 1; j >= 0; j--) {
      for (int i = j - 1; i >= 0; i--) {
        if (has(a[i] + a[j], pos)) {
          dp[i][j] = dp[j][cnt[pos]] + 1;
        }
        if (dp[i][j] > ret) {
          x = a[i];
          y = a[j];
          ret = dp[i][j];
        }
      }
      insert(a[j], j);
    }
    printf("%d\n", ret + 1);
    printf("%d", x);
    for (int i = 0; i < ret; i++) {
      printf(" %d", y);
      swap(x, y);
      y += x;
    }
    puts("");
  }
  return 0;
}