题解 P5948 【[POI2003]Chocolate】

Great_Influence

2020-01-20 21:38:40

Solution

发现数据范围是 $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]); } ```