[문제] CF883I: Photo Processing

12213 단어 문제풀이codeforces이분dp
원제 전송문은 우선 순서의 최대치를 가장 작게 배열하고 2점을 사용한 다음에 dp로 dpi dp 를 검증한다i dpi는 현재 i i i 임을 나타내며 마지막 그룹이 i i i 로 끝날 수 있는지 d p i ∣ = d p j - 1 (j < i, a i - a j < = m i d) dpi|=dp_{jj-1}(jpi∣=dpj는 1(jj)(i, j)(i, j)(i>j)(i, j)(i>j)(i>j)(i>j)[j, i] [j, i] [j, i] [j, i][j, i]]가 한 조로 나누지 못하면 [j, i+1] [j+1] [jj, j] [jj + 1](jj + 1} j [jj 1} 1} (jj j j 1} (j [j j j j j 1} [j j지침 l l l l 은 최소한 이 i i 로 전환될 수 있는r = i -3 m + 1 r = i-m +1 r = i -3 m +1 매번 d p l -3 1 = 0 이면 + l dp{l-1}=0,++l dpl−1​=0,++l
Code: 
#include 
#define maxn 300010
#define LL long long
using namespace std;
int a[maxn], dp[maxn], n, m;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool check(int mid){
	dp[0] = 1;
	int l = 1, r;
	for (int i = 1; i <= n; ++i){
		dp[i] = 0;
		while (a[i] - a[l] > mid) ++l;
		r = i - m + 1;
		for (int j = l; j <= r; ++j, ++l)
			if (dp[j - 1]){ dp[i] = 1; break; }
	}
	return dp[n];
}

int main(){
	n = read(), m = read();
	if (m == 1) return puts("0"), 0;
	for (int i = 1; i <= n; ++i) a[i] = read();
	sort(a + 1, a + 1 + n);
	int l = 0, r = a[n] - a[1], ans = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid - 1, ans = mid; else l = mid + 1;
	}
	printf("%d
", ans);
	return 0;
}
TextView 문자열이 가운데에 있지 않아서 슬퍼요
[Go] 마초는'근육맨'이 아니에요.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage