P1052 강 건너기(상태 압축 dp)

10277 단어 동적 기획
https://www.luogu.org/problemnew/show/P1052
문제풀이
상태 이동 방정식dp[i] = dp[i-k]+stone[i], s <= k <= t을 쉽게 얻어낼 수 있다.그중 i 대표는 i까지 걸어갈 때 돌을 몇 개 밟았는가.30퍼센트의 데이터에 대해 직접 이렇게 하면 된다.그러나 데이터 범위10^9는 메모리가 전혀 부족하다.자세히 살펴보면 최대 100개의 돌만 있고 매번 뛰는 거리는 최대 10개 단위로 그 안에 돌이 없는 거리가 매우 큰 것이 분명하다.여기에 작은 지식이 필요합니다: lcm(1,2,3,4,5,6,7,8,9,10) = 2520.즉 0부터 아무리 뛰어도 결국 2520까지 뛴다.그래서 두 돌 사이의 거리가 2520을 넘으면 나머지 것을 얻을 수 있다. 예를 들어 0에서 2521까지 뛰면 아무리 뛰어도 2520까지 뛴다. 그러면 0에서 1까지 뛰는 셈이다.이렇게 압축된 경로의 크기는 100*2520을 초과하지 않는다.
코드
#include 
using namespace std;
const int maxn = 250000+100;
const int INF = 0x3f3f3f;
// dp[i] = dp[i-k]+stone[i]; s <= k <= t
int a[maxn],d[maxn],stone[maxn],dp[maxn];
int main() {
	int L,S,T,M;
	scanf("%d", &L);
	scanf("%d%d%d", &S, &T, &M);
	for(int i = 1; i <= M; ++i) 
		scanf("%d", &a[i]);
	sort(a+1,a+1+M);
	for(int i = 1; i <= M; ++i) 
		d[i] = (a[i]-a[i-1])%2520;
	for(int i = 1; i <= M; ++i) {
		a[i] = a[i-1]+d[i];
		stone[a[i-1]+d[i]] = 1;
	}
	int r = a[M];
	memset(dp, INF, sizeof dp);
	dp[0] = 0;
	int ans = INF;
	for(int i = 1; i <= r+T; ++i) {
		for(int j = S; j <= T; ++j) {
			if(i-j >= 0)
				dp[i] = min(dp[i], dp[i-j]+stone[i]);
			if(i >= r)
				ans = min(ans, dp[i]);
		}
	}
	cout << ans << endl;
	return 0;
}
링크 ux 아래 iptables 방화벽 설정 노트
ngx_http_process_request_line 함수 해석

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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