题解 P1281 【书的复制】

皎月半洒花 · 2019-01-03 17:59:32 · 题解

一个区间DP

\rm{OxO1} 前言

事实上，如果按照常规思路的话……这个题应该是一个\Theta(n^4)的区间DP——首先两遍循环枚举左端点L\&R，一重循环枚举中间点，一重之后枚举K……

$$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:

#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 ;
}