题解 P5948 【[POI2003]Chocolate】
Great_Influence
2020-01-20 21:38:40
发现数据范围是 $10^4$ ,显然是 $O(nm)$ 卡一卡能过的。
注意到我们每一维肯定都是从大到小一刀刀切, 排完序后就只需要考虑横着切和竖着切的相对顺序了。
写个 $O(nm)$ 的 $dp$ 就可以了。注意最好将第一维滚动节省访问数组的时间。
按照题意模拟会 TLE ?
我们先分析一下原来的 $dp$ 方程:
$$dp[i][j] = \min(dp[i-1][j]+a[i]*j,dp[i][j-1]+b[j]*i)$$
容易发现瓶颈在于 $O(nm)$ 次的乘法。我们考虑利用后缀和将乘法优化成加法:
$$dp[i][j] = \min(dp[i-1][j]+B[j+1],dp[i][j-1]+A[i+1])$$
这个式子是怎么来得呢? 我们考虑横着切完这一刀后,后面竖着的没切的每一刀的相对顺序都会向后移动一格,每一个所乘的系数都会 $+1$ 。我们将初值设置为 $dp[0][0]=A[1]+B[1]$ ,那么所要的答案就是 $dp[n][m]$ 。
这样会比直接使用乘法快大概10倍左右。~~(当然你要是用 $O2$ 乘法也许也能跑过去。。。)~~
核心代码:
```cpp
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
sort(a + 1, a + n + 1, greater<int>());
sort(b + 1, b + m + 1, greater<int>());
Repe(i, n - 1, 1) a[i] += a[i + 1];
Repe(i, m - 1, 1) b[i] += b[i + 1];
dp[0][0] = a[1] + b[1];
Rep(i, 1, m) dp[0][i] = dp[0][i - 1] + a[1];
cr = dp[0];
Rep(i, 1, n)
{
ls = cr, cr = dp[i & 1];
cr[0] = ls[0] + b[1];
Rep(j, 1, m) cr[j] = min(ls[j] + b[j + 1], cr[j - 1] + a[i + 1]);
}
```