오름차순으로 정렬 되 있는 타일이 주어진다.
이 타일 안에서 등차수열의 수가 3개 이상인 집합의 최대 합을 구하는 문제이다.
$DP[from][to]$ : $from$이 첫번째 항이고 공차가 $arr[to]-arr[from]$일 때 최대합
위와 같이 점화식을 세우면 풀 수 있다.
집합의 수가 3개 이상이므로 재귀함수를 두번 통과하면 flag를 true로 주어 반환하면 된다.
long long 형으로 주어서 flag를 포함시키는 3차원 dp로 만들면 메모리초과가 난다.
#include <cstdio>
#include <cstring>
#define max(a,b) ((a)<(b)?(b):(a))
typedef long long ll;
int N;
int arr[3001];
int pre[1000001];
ll dp[3001][3001];
ll solve(int from, int to, bool flag) {
ll &ret = dp[from][to];
if (ret != -1) return ret;
ret = 0;
ll diff = arr[to] - arr[from];
if (arr[to] + diff > 1000000 || pre[arr[to] + diff] == -1) {
if (flag) return ret = arr[from] + arr[to];
else return ret;
}
else {
int next = pre[arr[to] + diff];
return ret = arr[from] + solve(to, next, 1);
}
}
int main() {
memset(dp, -1, sizeof dp);
memset(pre, -1, sizeof pre);
scanf("%d", &N);
for (int n = 0;n < N;n++) {
scanf("%d", &arr[n]);
pre[arr[n]] = n;
}
ll ans = 0;
for (int n = 0;n < N;n++) {
for (int m = n + 1;m < N;m++)
ans = max(ans, solve(n, m, 0));
}
printf("%lld\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기