【DP】fish
WeLikeStudying · · 题解
- 珍惜这道近年来比较简单的 IOI 题！
题意
- 有一个
n\times n 的网格，里面有m 条鲶鱼，都有各自的重量。 - 你可以建一些从
(x,0) 到(x,y) 的堤，如果鲶鱼在(x,y) 处，那么它被捕获当且仅当(x-1,y) 或(x+1,y) 处有堤且(x,y) 处没堤。 - 求可捕获鲶鱼的最大总重量，
n\le 10^5,m\le 3\times 10^5 。
分析
- 考虑
O(n^2) 的暴力怎么做，尝试按行 DP，你发现或这个条件比较丑陋，且只考虑一种情况（对于第i 行的贡献，只考虑第i-1 行的帮助或第i+1 行的帮助）并没有影响。 - 设
f(i,j,0/1) 为第i 行建(i,0) 到(i,j) 的坝，前i-1/i 行能抓到的最大重量，则（设g(i,j) 为(i,0) 到(i,j) 的鲶鱼质量之和），拆掉 DP 式子里面无用的东西，则：f(i,j,0)+g(i,k)-g(i,j)\to f(i+1,k,0) f(i,j,1)\to f(i+1,k,0) f(i,j,1)+g(i+1,j)-g(i+1,k)\to f(i+1,k,1) - 直接这样 DP 是
O(n^3) 的，但是参变分离下，可以发现它是O(n^2) 的。 - 由于鲶鱼很少，本质不同的状态也很少，所以我们可以做到
O(n+m) ，虽然没必要，代码。