発電計画問題

問題

dp[t]
時刻 t までの総利得の最大値

区間[ i~j ]の利得はg[i][j-1]である

// 入力
int T1;
int g[110][110];

// DP テーブル
int dp[110];

int main() {
    cin >> T1; //時刻
    for (int i = 0; i < T1; ++i) for (int j = 0; j < T1; ++j) cin >> g[i][j]; //利得

    // DP テーブル初期化
    memset(dp, 0, sizeof(dp));

    // DP ループ
    for (int t = 1; t <= T1 + 1; ++t) { //時間
        for (int i = 0; i < t; ++i) { //始まり
            for (int j = i + 1; j < t; ++j) { //終わり
                dp[t] = max(dp[t], dp[i] + g[i][j - 1]); //すべての区間を試す
            }
        }
    }
    cout << dp[T1 + 1] << endl; //g[i][j - 1]より
}