各読書プランでは番号の昇順に本を読み、途中でやめてもよいとします。 これによって答えが変わることはありません。

\(\operatorname{dp} _ j[i][k]\coloneqq i\) 番目までの本を、\(j\) 番目までの読書プランのうち \(k\) 個まで選んで読むときに読むことができる本の種類の最大値 \((0\le i\le N,0\le j\le M,0\le k\le K)\) とします。 これは、次のような式で計算することができます。 \[\operatorname{dp} _ j[i][k]=\begin{cases}0&(i=0\vee j=0\vee k=0)\\\operatorname{dp} _ {j-1}[i][k]&(i\lt L _ i)\\\max\lbrace\operatorname{dp} _ {j-1}[i][k],\operatorname{dp} _ {j-1}[L _ j][k-1]+i-L _ j\rbrace&(L _ j\le i\le R _ j)\\\max\lbrace\operatorname{dp} _ {j-1}[i][k],\operatorname{dp} _ {j-1}[L _ j][k-1]+R _ j-L _ j+1\rbrace&(R _ j\lt i)\end{cases}\]

これをそのまま実装すると時間・空間計算量がともに \(\Theta(NMK)\) となってしまいます。

\(j,k\) を固定したとき、\(\operatorname{dp} _ j[i][k]\) が有限個の \(2\) つ組 \(((x _ 1,y _ 1),(x _ 2,y _ 2),\ldots,(x _ n,y _ n))\) によって \[\operatorname{dp} _ j[i][k]=\max _ {1\le l\le n}\min\lbrace i+y _ l,x _ l+y _ l\rbrace\] と表せることに着目します（これは上の式を使って帰納法を使うことで、\(\operatorname{dp} _ j[i][k]\ge\operatorname{dp} _ j[i][k-1]\) とあわせて示すことができます）。

\(j,k\) に対して上の式を満たす \(2\) つ組の集合を \(S _ {j,k}\) とします。 上に示した DP の遷移の式から、\(S _ {j,k}=S _ {j-1,k}\cup\lbrace(R _ i+1,\operatorname{dp} _ {j-1}[L _ j][k-1]-L _ j)\rbrace\) とできることがわかります。

DP テーブルそのものの代わりに \(S _ {j,k}\) を管理することによって、時間計算量を \(\Theta(M ^ 2K)\) とすることができます。 \(S _ {j,k}\) を \(\operatorname{dp} _ j[i][k]\) の値が計算しやすいように管理することでこの問題を解くことができます。 具体的には、\(S _ {j,k}\) を平衡二分探索木を使って管理したり、読書プランを \(R _ i\) の昇順に並べ替えて \(S _ {j,k}\) をスタックを使って管理することで時間計算量を \(O(KM\log M)\) などとすることができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    // DP テーブルを 2 つ組の列 vector<pair<int, int>> で表す
    // y の降順に並べ、最大値を取らないものも取り除いておく

    // 列から dp[i] を求める関数
    auto access{[](vector<pair<int, int>>& table, int i) {
        auto it = ranges::lower_bound(table, make_pair(i, 0)); // 二分探索をして
        int ret = 0;
        if (it != table.end()) {
            // i + y のほうと
            ret = i + it->second;
        }
        if (it != table.begin()) {
            // x + y のほうの最大値を求める
            ret = max(ret, prev(it)->first + prev(it)->second);
        }
        return ret;
    }};
    // 列に組 (x, y) を追加する関数
    auto add{[](vector<pair<int, int>>& table, int x, int y) {
        // 最大値を取る可能性があれば
        if (table.empty() || table.back().first + table.back().second < x + y) {
            // y が小さいものを取り出して
            while (!table.empty() && table.back().second <= y) {
                table.pop_back();
            }
            table.emplace_back(x, y); // 追加する
        }
    }};

    vector<pair<int, int>> intervals(M);
    for (auto& [L, R] : intervals) {
        cin >> L >> R;
        --L; // 0-indexed 右半開区間にしておく
    }

    // R の値でソート
    ranges::sort(intervals, {}, [](pair<int, int> p){return p.second;});

    vector dp(K + 1, vector<pair<int, int>>{{0, 0}});
    for (auto [L, R] : intervals) {
        for (int k = K; k > 0; --k) {
            add(dp[k], R, access(dp[k - 1], L) - L);
        }
    }
    cout << access(dp.back(), N) << endl;
    return 0;
}

from bisect import bisect_left


N, M, K = map(int, input().split())

# DP テーブルを 2 つ組の列 vector<pair<int, int>> で表す
# y の降順に並べ、最大値を取らないものも取り除いておく

# 列から dp[i] を求める関数
def access(table, i):
    index = bisect_left(table, (i, 0)) # 二分探索をして
    ret = 0
    if index != len(table):
        # i + y のほうと
        ret = i + table[index][1]
    if index != 0:
        # x + y のほうの最大値を求める
       ret = max(ret, table[index - 1][0] + table[index - 1][1])
    return ret

# 列に組 (x, y) を追加する関数
def add(table, x, y):
    # 最大値を取る可能性があれば
    if len(table) == 0 or table[-1][0] + table[-1][1] < x + y:
        # y が小さいものを取り出して
        while len(table) > 0 and table[-1][1] <= y:
            table.pop()
        table.append((x, y)) # 追加する

intervals = []
for i in range(M):
    L, R = map(int, input().split())
    L -= 1 # 0-indexed 右半開区間にしておく
    intervals.append((L, R))

# R の値でソート
intervals.sort(key=lambda x: x[1])

dp = [[(0, 0)] for i in range(K + 1)]
for L, R in intervals:
    for k in range(K, 0, -1):
        add(dp[k], R, access(dp[k - 1], L) - L)

print(access(dp[-1], N))