HDU 4293 Groups：區間 DP 最大化真實信息數

問題描述

n 人排成一排，每人給出 (a, b) 表示「我所在組前面有 a 人，後面有 b 人」。若 a+b ≥ n 則必定撒謊。將同一區間 [a+1, n-b] 的人數統計為 Map[l][r]，但該區間最多容納 n - (l-1) - (n-r) = r-l+1 人，超出則截斷。現從中選取若干不相交區間，使權值之和最大。

轉化為區間加權選取

• 預處理：對每人，若 a+b < n，則 l=a+1, r=n-b，Map[l][r]++，並 Map[l][r] = min(Map[l][r], r-l+1)。
• DP：dp[i] 表示前 i 列最大權值。dp[i] = max(dp[i-1], max_{j≤i} (dp[j-1] + Map[j][i]))。

複雜度

• 預處理 O(n)。
• DP O(n^2)，n ≤ 500 完全可行。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int Map[MAXN][MAXN], dp[MAXN];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    while (cin >> n) {
        memset(Map, 0, sizeof(Map));
        for (int i=1;i<=n;i++) {
            int a,b; cin>>a>>b;
            if (a+b >= n) continue;
            int l = a+1, r = n-b;
            Map[l][r] = min(Map[l][r]+1, r-l+1);
        }
        memset(dp, 0, sizeof(dp));
        for (int i=1;i<=n;i++) {
            dp[i] = dp[i-1];
            for (int j=1;j<=i;j++)
                dp[i] = max(dp[i], dp[j-1] + Map[j][i]);
        }
        cout << dp[n] << '\n';
    }
    return 0;
}