'BZOJ4300'절세호제.
n 길이의 수열ai를 정하고ai의 하위 서열bi의 가장 긴 길이를 구하여bi&b(i-1)를 만족시킵니다!0(2<=i<=len).
입력 형식
입력 파일은 모두 두 줄입니다.
첫 번째 줄은 정수 n을 포함한다.
두 번째 줄은 n개의 정수를 포함하고, 두 번째 정수는ai를 표시한다.
출력 형식
출력 파일은 한 줄입니다.
하위 서열bi의 가장 긴 길이를 나타내는 정수를 포함합니다.
예제
샘플 입력
1 2 3
样例输出
数据范围与提示
n<=100000,ai<=2*10^9
， LIS。
：
f[i] = max(f[i], f[j] + 1)i:1~n,j:1~i-1
#include
#include
using namespace std;
const int M = 1e5 + 5;
int a[M], f[M];
int main() {
int n, ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
f[i] = 1; //
scanf("%d", &a[i]);
for(int j = 1; j < i; j ++) {
int temp = a[i] & a[j];
if(temp != 0) { //
f[i] = max(f[i], f[j] + 1);
}
}
}
for(int i = 1; i <= n; i ++) {
ans = max(ans, f[i]);
}
printf("%d", ans);
return 0;
}
제출, Time Limit Exceeded
dp[i][j] i ， i j
temp i
f[j]
：dp[i]=max(f[i],f[j]+1),a[i]&(1<#include
#include
using namespace std;
const int M = 1e3 + 5;
int a[M], f[M][M];
int main() {
int n, ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
int temp = 1;
for(int j = 1; j <= 32; j ++) {
if(a[i] & (1 << (j - 1))) {
temp = max(temp, f[i - 1][j] + 1);
for(int k = 1; k <= j; k++) { //
if (a[i] & (1 << (k - 1))) {
f[i][k] = temp;
}
}
}
}
// for(int j = 1; j <= 32; j ++) {
// if(a[i] & (1 << (j - 1))) {
// f[j] = max(f[j], temp);
// }
// }
ans = max(ans, temp);
}
printf("%d", ans);
return 0;
}
다시 한 번 건네주다
Accepted
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
