백준 16494 가장 큰 값

https://www.acmicpc.net/problem/16494

16494번: 가장 큰 값

이전에 생각 안 난 문제를 적어두었는데 사람들이 유입되길래 풀어봄 

 

 문제 조건에서 빠진 부분이 있는데 중복된 index를 뽑을 수는 없다. 

 

문제는 M개의 그룹을 뽑을 때 그 그룹 합의 최대를 구하는 문제이다. 

모든 i,j 쌍에 대해서 누적합을 구한 뒤, dp식을 세운다.

 

dp[i][j] := [i, j]에서의 연속된 수열의 최대 합 

따라서 N^4으로 dp테이블을 만들 수 있다. 

 

그 다음에 1~N까지 중 M개의 그룹을 뽑는 모든 경우에 대해서 계산하면 된다.

이번에 이 문제를 풀면서 Next Permutation 함수를 처음으로 구글링해서 써보았는데 아주 편하다. 

 

--------------------------------------------------------------------------------------------------------------

1~N개의 그룹으로 이루어진 것 모든 경우에 대해서 브루트포스 계산도 가능하다. 
시간복잡도 O(2^N)

N = 20이므로 가능 

#include <bits/stdc++.h>
using namespace std;
#define TEST int tt; cin >> tt; while (tt--)
#define all(v) (v).begin(), (v).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define ll long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0);
const int MAX = 200'005;
const int INF = 1e9 + 1;
const ll MOD = 1'000'003;

int num[50];
int sum[50][50];
int dp[40][40];


int main() {
    FASTIO
    int N, M;
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        cin >> num[i];
    }
    for(int i=1; i<=N; i++){
        for(int j=i; j<=N; j++)dp[i][j] = -INF;
    }
    vector<int> v;
    for(int i=0; i<N; i++){
        for(int j=1; j<=N; j++){
            if(j+i>N)break;
            sum[j][j+i] = sum[j][j+i-1] + num[j+i];
        }
    }
    for(int i=1; i<=N; i++){
        for(int j=i; j<=N; j++){
            for(int a=i; a<=j; a++){
                for(int b=a; b<=j; b++){
                    dp[i][j] = max(dp[i][j], sum[a][b]);
                }
            }
        }
    }
    vector<int> a;
    vector<int> b;
    int cnt = 0;
    for(int i=1; i<=N; i++){
        a.emplace_back(i);
        if(cnt<M-1){
            b.emplace_back(1);
            cnt++;
        }
        else b.emplace_back(0);
    }
    int before;
    int ans = -INF;
    do {
        int sum =0;
        before = 1;
        for (int i = 0; i < a.size(); ++i) {
            if (b[i] == 1){
                sum += dp[before][a[i]];
                before = a[i]+1;
            }
        }
        if(before<=N){
            sum+=dp[before][N];
            ans = max(ans, sum);
        }
    } while (prev_permutation(b.begin(), b.end()));
    cout << ans;
}