Codeforces-813D Two Melodies(dp)
3218 단어 DP
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Alice is a beginner composer and now she is ready to create another masterpiece. And not even the single one but two at the same time!
Alice has a sheet with n notes written on it. She wants to take two such non-empty non-intersecting subsequences that both of them form a melody and sum of their lengths is maximal.
Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
Subsequence forms a melody when each two adjacent notes either differs by 1 or are congruent modulo 7.
You should write a program which will calculate maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.
Input
The first line contains one integer number n (2 ≤ n ≤ 5000).
The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 105) — notes written on a sheet.
Output
Print maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.
Examples
input
4
1 2 4 5
output
4
input
6
62 22 60 61 48 49
output
5
Note
In the first example subsequences [1, 2] and [4, 5] give length 4 in total.
In the second example subsequences [62, 48, 49] and [60, 61] give length 5 in total. If you choose subsequence [62, 61] in the first place then the second melody will have maximum length 2, that gives the result of 4, which is not maximal.
dp[i][j]를 두 개의 하위 서열의 끝으로 각각 i와 j의 최대 총산도를 설정하면 ij를 합쳐서 i를 열거할 수 있다. 그러면 현재 j는 이미 첫 번째 하위 서열에 의해 선택되었을 수도 있다.dp[i][j]와 dp[j][i]가 같기 때문에 매번 dp[i][j]를 업데이트할 때마다 dp[j]=dp[i][j]로 하여금 자연스럽게 i>j의 상황을 구할 수 있다.
#include
#define x first
#define y second
using namespace std;
typedef long long LL;
const int MX = 5005;
const int MXM = 1e5 + 5;
int dp[MX][MX]; //dp[i][j] i,j 2
int a[MX], pre[MXM], mod[8];
int main() {
//freopen("in.txt", "r", stdin);
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 0; i <= n; i++) { // i, j,
memset(pre, 0, sizeof(pre));
memset(mod, 0, sizeof(mod));
for (int j = 1; j < i; j++) {
pre[a[j]] = max(pre[a[j]], dp[i][j]);//pre a[j]
mod[a[j] % 7] = max(mod[a[j] % 7], dp[i][j]);//mod 7
}
for (int j = i + 1; j <= n; j++) {
dp[i][j] = max(pre[a[j] + 1], pre[a[j] - 1]) + 1;
dp[i][j] = max(dp[i][j], mod[a[j] % 7] + 1);
dp[i][j] = max(dp[i][j], dp[i][0] + 1);
dp[j][i] = dp[i][j]; //
pre[a[j]] = max(pre[a[j]], dp[i][j]);
mod[a[j] % 7] = max(mod[a[j] % 7], dp[i][j]);
ans = max(ans, dp[i][j]);
}
}
printf("%d
", ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.