bzoj4985(2점+dp)
p[i]: i가 마지막 수일 때, 그리고 i>=x, 앞에 추가해야 할 >=x의 수;
만약 dp[마지막 개수]가 필요로 하는 >=x의 개수 <=위치의 수를 모르면 합법적이다.
dp[1-n]는 모두 최초의 상태이다.
만약 i 위치의 수가 =x라면, 값은 inf입니다
만약 i 위치의 수가 >=x이면 그 자체가 >=x이기 때문에 값은 0이다.
i 위치의 수를 알 수 없으면 1을 부여합니다.
그 다음에 시뮬레이션을 해서 매번 팀의 첫 번째 세 개를 뽑고 가장 작은 두 개의 수를 합쳐서
만약 두 수의 화=x의 수가 있다면 새로운 팀의 끝도 반드시 >=x가 될 수 있다.dp[++tail] = 두 수의 합
하면, 만약, 만약...
#include
#include
#include
#include
using namespace std;
int a[200000], b[200000],c[200000], n, m;
long long dp[600000];
int check(int x)
{
memset(dp,0,sizeof(dp));
int shu = 0;
for(int i = 1; i <= n - m; i++)
{
if(b[i] >= x) shu ++;
}
for(int i = 1; i <= n; i++)
{
if(a[i] == 0) dp[i] = 1;
else if(a[i] >= x) dp[i] = 0;
else dp[i] = 1e9;
}
int head = 1, tail = n;
while(head + 1< tail)
{
long long t = dp[head + 1] + dp[head] + dp[head + 2];
long long ha = max(dp[head + 1], dp[head]);
ha = max(dp[head + 2], ha);
if(t - ha > 1e9)dp[++tail] = 1e9;
else dp[++tail] = t - ha;
head += 3;
}
if(dp[tail] > shu) return 0;
return 1;
}
int main()
{
cin >> n >> m;
int cnt = 0;
for(int i = 1; i <= m; i++)
{
int d, v;
scanf("%d%d",&v,&d);
a[d] = v;
c[++cnt] = v;
}
for(int i = 1; i <= n - m; i++)
{
scanf("%d",&b[i]);
c[++cnt] = b[i];
}
sort(1+c,1+c+cnt);
int ans = 0,l = 1, r = cnt;
while(l <= r)
{
int mid = (l + r) / 2;
if(check(c[mid]) == 1)
{
l = mid + 1;
ans = c[mid];
}
else r = mid - 1;
}
cout << ans;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
