#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n, k, a[2001], dp[2001][2001], s, res; int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", a + i), s += a[i]; if (2 * k >= n) { printf("%d", s); return 0; } for (int i = 1; i <= k; i++) { int maxi = 0; for (int j = i; j <= n; j++) { maxi = max(maxi, dp[i - 1][j - 1]); dp[i][j] = maxi + a[j]; if (i > 1 && j > i) dp[i][j] = max(dp[i][j], dp[i - 1][j - 2] + a[j] + a[j - 1]); } } for (int i = k; i <= n; i++) res = max(res, dp[k][i]); memset(dp, 0, sizeof(dp)); dp[1][1] = a[1]; for (int i = 2; i <= n; i++) dp[1][i] = -2e9; for (int i = 2; i <= k; i++) { int maxi = 0; for (int j = i; j <= n; j++) { maxi = max(maxi, dp[i - 1][j - 1]); dp[i][j] = maxi + a[j]; if (i > 1 && j > i) dp[i][j] = max(dp[i][j], dp[i - 1][j - 2] + a[j] + a[j - 1]); } } for (int i = 1; i < k; i++) { int maxi = 0; for (int j = k - i; j <= n - 2 * i; j++) maxi = max(maxi, dp[k - i][j]); for (int j = n - 2 * i + 1; j <= n; j++) maxi += a[j]; res = max(res, maxi); } rotate(a + 1, a + 2, a + 1 + n); memset(dp, 0, sizeof(dp)); dp[1][1] = a[1]; for (int i = 2; i <= n; i++) dp[1][i] = -2e9; for (int i = 2; i <= k; i++) { int maxi = 0; for (int j = i; j <= n; j++) { maxi = max(maxi, dp[i - 1][j - 1]); dp[i][j] = maxi + a[j]; if (i > 1 && j > i) dp[i][j] = max(dp[i][j], dp[i - 1][j - 2] + a[j] + a[j - 1]); } } for (int i = 1; i < k; i++) { int maxi = 0; for (int j = k - i; j <= n - 2 * i; j++) maxi = max(maxi, dp[k - i][j]); for (int j = n - 2 * i + 1; j <= n; j++) maxi += a[j]; res = max(res, maxi); } printf("%d", res); return 0; }
7984번: Rabbits
https://www.acmicpc.net/problem/7984
라벨:
다시풀예정
,
BOJ
,
dynamic programming
피드 구독하기:
댓글
(
Atom
)
댓글 없음 :
댓글 쓰기