8.31集训

今天做了三个dp 第一个是子串

状态：设\(f[i][j][p][0/1]\)表示a串前i位使用p个子串匹配b串前j位字符且第i个位置选/不选的方案数

转移：

• 当\(a[i]=b[j]\)
• \(f[val][j][p][0]=(f[val\;xor\;1][j][p][0]+f[val\;xor\;1][j][p][1])\%mod\)
• \(f[val][j][p][1]=(f[val\;xor\;1][j-1][p][1]+(f[val\;xor\;1][j-1][p-1][0]+f[val\;xor\;1][j-1][p-1][1])\%mod)\%mod\)
• 当\(a[i]\neq[j]\)
• \(f[val][j][p][0]=(f[val\;xor\;1][j][p][0]+f[val\;xor\;1][j][p][1])\%mod\)
• \(f[val][j][p][1]=0;\)

时间复杂度\(O(n^3)\)，空间复杂度\(O(m\times k)\)

因此需要优化空间，发现第一维\(i\)只与\(i-1\)有关系，所以把\(i\)这一维度滚掉

方法：\(val\)是当前的\(i\)，而\(val\;xor\;1\)是\(i-1\)，总之就是转移方程的时候另一个数

每次都\(xor\;1\)，然后答案就是\(n\&1\)，感觉很奇妙。。。。

注意：这种情况下，\(val\)初始为1

第二个是换教室

一道极其好，但是极其难做的题

坑点：

1.弗洛伊德

有向图和无向图写法不一样

有向图：

Code

memset (dis, 0x3f, sizeof dis);
for (i = 1; i <= n; ++ i) dis[i][i] = 0;
for (k = 1; k <= n; ++ k)
   for (i = 1; i <= n; ++ ｉ)
      for (j = 1; j <= n; ++ j)
         dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

无向图：

Code

for (i = 1; i <= n; ++ i)
   for (j = 1; j < i; ++ j)
      dis[i][j] = dis[j][i] = inf;
for (i = 1; i <= e; ++ i)
{
   cin >> x >> y >> z;
   dis[x][y] = dis[y][x] = min(dis[x][y], z);
}
for (e = 1; e <= v; ++ e)
   for (i = 1; i <= v; ++ i)
      for (j = 1; j < i; ++ j)
         dis[i][j] = dis[j][i] = min(dis[i][j], dis[i][e] + dis[e][j]);

2.只在memset里面用0x3f，0x7f，其中\(0x7f\)比\(0x3f\)大一倍，\(0x7f\)约为2147483647

在平时不要用赋值语句，或者直接输出将会得到\(63\;or\;127\)

其中0x7fffffff，为2147483647

第三道，飞扬的小鸟

状态：\(f[i][j]\)表示横坐标为i时高度为j的最少点击次数

转移：

• 上升的话是完全背包，因为可以一直点
• 下降的话，是01背包

其中转移顺序的话，先升再降，超过m变为m——特判