题解 P1281 【书的复制】
皎月半洒花
2019-01-03 17:59:32
一个区间$DP$
## $\rm{OxO1}$ 前言
事实上，如果按照常规思路的话……这个题应该是一个$\Theta(n^4)$的区间$DP$——首先两遍循环枚举左端点$L\&R$，一重循环枚举中间点，一重之后枚举$K$……
$\rm{However}$，有动规经验的人都知道……左端点是可以不枚举的，因为我们最终询问的是$[1,N]$的，所以可以优化到$\Theta(n^3)$……方程如下：
$$dp_{i,j}=\min\{\max(dp_{k,j-1},\rm{S}[k+1,i])\}_{(0\leq k < i)}$$
其中$\rm{S}$表示求区间和。
我写的代码大概长这样：
```cpp
int main(){
memset(dp, 63, sizeof(dp)) ;
cin >> N >> M ; dp[0][0] = 0 ;
for (i = 1 ; i <= N ; ++ i)
cin >> base[i], S[i] = S[i - 1] + base[i] ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j)
for (k = 0 ; k < i ; ++ k){
if (dp[i][j] > (t = max(dp[k][j - 1], S[i] - S[k])))
dp[i][j] = t, F[i][j] = k + 1 ;
}
t = N, i = M, k = 0 ;
while (F[t][i])
s.push(t), t = ((1 & k)) ? t - 1 : F[t][i], i = ((1 & k)) ? i - 1 : i, ++ k ;
while (1){
if (!s.empty())
cout << s.top() << " ", s.pop() ;
else break ;
if(!s.empty())
cout << s.top() << endl, s.pop() ;
else break ;
}
}
```
呃，至于输出路径，看个人喜好……但是笔者这里想说的问题是这个代码只有$70pts$……原因是题目里有个很坑人的地方：
>如果有多解，则尽可能让前面的人少抄写。
这就很$GG$……不知道为什么，似乎我这种方法$DP$出来的东西和std不同……并且好像std自动带了解决这个问题的功能……于是——
## $\rm{OxO2}$ 乱搞
下面进入乱搞环节。
起初我想的是一个贪心：如果相邻两个区间的长度都不是答案，那么他们对答案没有贡献，那么我们就可以在合理的范围内让前面的区间的$value$更小，后面的$value$更大，所以我一开始把区间存了下来，并写了个$for$循环：
```cpp
inline void update(int x){
r[x].Len = S[r[x].R] - S[r[x].L - 1] ;
}
************
while (1){
if (!s.empty()) r[++ j].L = s.top(), s.pop() ;
if (!s.empty()) r[j].R = s.top(), s.pop() ; else break ;update(j) ;
}
for (i = 1 ; i < j ; ++ i){
while (r[i].Len <= Max && r[i + 1].Len <= Max && r[i].L < r[i].R) {
r[i].R --, r[i + 1].L --, update(i), update(i + 1) ;
}
if (r[i + 1].Len > Max) r[i].R ++, r[i + 1].L ++, update(i), update(i + 1) ;
}
```
事实上，他依旧不对，只有$80pts$。原因也很简单，相邻的区间可以互相补给，但是如果之后的区间发生了改变，单纯的$for$无法处理……所以我又写了个$dfs$:
```cpp
inline void dfs(int E){
for (int ii = 1 ; ii < E ; ++ ii){
int mark = 0 ;
while (r[ii].Len <= Max && r[ii + 1].Len <= Max && r[ii].L < r[ii].R)
r[ii].R --, r[ii + 1].L --, update(ii), update(ii + 1), mark ++ ;
if (r[ii + 1].Len > Max)
mark --, r[ii].R ++, r[ii + 1].L ++, update(ii), update(ii + 1) ;
if (mark) dfs(E - 1) ;
}
}
```
然后他就$AC$了……2333……不过其实这个输出只是个小暴力而已.
所以，这篇题解是一篇乱搞题解……$qwq$
$Code:$
```cpp
#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 600
struct range{
int L, R, Len ;
}r[MAXN] ; int Max ;
using namespace std ; int i, j, k, t ; stack <int > s ;
int N, M, base[MAXN], S[MAXN], F[MAXN][MAXN], dp[MAXN][MAXN] ;
inline void update(int x){
r[x].Len = S[r[x].R] - S[r[x].L - 1] ;
}
inline void dfs(int E){
for (int ii = 1 ; ii < E ; ++ ii){
int mark = 0 ;
while (r[ii].Len <= Max && r[ii + 1].Len <= Max && r[ii].L < r[ii].R)
r[ii].R --, r[ii + 1].L --, update(ii), update(ii + 1), mark ++ ;
if (r[ii + 1].Len > Max)
mark --, r[ii].R ++, r[ii + 1].L ++, update(ii), update(ii + 1) ;
if (mark) dfs(E - 1) ;
}
}
int main(){
memset(dp, 63, sizeof(dp)) ;
cin >> N >> M ; dp[0][0] = 0 ;
for (i = 1 ; i <= N ; ++ i)
cin >> base[i], S[i] = S[i - 1] + base[i] ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j)
for (k = 0 ; k < i ; ++ k){
if (dp[i][j] > (t = max(dp[k][j - 1], S[i] - S[k])))
dp[i][j] = t, F[i][j] = k + 1 ;
}
Max = dp[N][M], t = N, i = M, k = 0, j = 0 ;
while (F[t][i]) s.push(t), t = ((1 & k)) ? t - 1 : F[t][i], i = ((1 & k)) ? i - 1 : i, ++ k ;
while (1){
if (!s.empty()) r[++ j].L = s.top(), s.pop() ;
if (!s.empty()) r[j].R = s.top(), s.pop() ; else break ; update(j) ;
}
dfs(j) ;
/*for (i = 1 ; i < j ; ++ i){
while (r[i].Len <= Max && r[i + 1].Len <= Max && r[i].L < r[i].R) {
r[i].R --, r[i + 1].L --, update(i), update(i + 1) ;
}
if (r[i + 1].Len > Max) r[i].R ++, r[i + 1].L ++, update(i), update(i + 1) ;
}*/
for (i = 1 ; i <= j ; ++ i) cout << r[i].L << " " << r[i].R << endl ;
}
```