#BZOJ4990

BZOJ4990 [Usaco2017 Feb]Why Did the Cow Cross the Road II 动态规划 树状数组

  有上下两行长度为n的数字序列A和序列B,都是1到n的排列,若abs(A[i]-B[j])<=4,则A[i]和B[j]间可以连一条边。现求在边与边不相交的情况下的最大连边数量。  我们用dp[i][j]表示枚举到A序列的第i个位置,与B序列的第j个位置匹配,所得到的最大效益,这样显然是要超时的,但是不妨去思考一...