POJ1038 Bugs Integrated, Inc. (状压DP)

题目链接: POJ1038 Bugs Integrated, Inc.
题目大意:

有 \(d\) 张 \(n*m\) 的硅片,上面有一些单元是坏的,求每张硅片最多能生产多少块 \(2*3\) 的芯片。
\(d\leq5\) , \(n\leq150\) , \(m\leq10\).
时限15000ms,空间限制30000kb
POJ1038 Bugs Integrated, Inc. (状压DP)

思路:
芯片的长度为3,则需要记录前两层的状态,考虑三进制状压 \(dp[i][j]\) 为到了第\(i\)行,此行状态为\(j\)时最多可放多少芯片,为了统计放了几块芯片,我们要记录当前行往上能不能放得下一块芯片,对于状态\(j\)的每一位\(j_k\):

  • \(j_k=0\) : \(a[i-1][k]\) 和 \(a[i][k]\) 都没有放东西
  • \(j_k=1\) : \(a[i-1][k]\) 放了东西,\(a[i][k]\) 没有放
  • \(j_k=2\) : \(a[i][k]\) 放了东西(此时 \(a[i-1][k]\) 状态不重要)

DP的时候记录 \(P\) 和 \(Q\) 数组为当前行和上一行的状态,dfs向下一行转移。
时间复杂度 \(O(d*C*m*3^m)\),\(C\) 为dfs转移的时间复杂度,\(m=10\)时 \(C\) 的上限为\(280\),由于这道题卡空间(约为29Mb),DP要滚动转移。

Code:
POJ1038 Bugs Integrated, Inc. (状压DP)

上一篇:代码审计-PHP_bugs(1)


下一篇:https://hdlbits.01xz.net/wiki/Finding Bugs in Code答案