글 읽기 - 2854번 문제 출제 질문입니다

pkc4913 4년 전 0

dp[n][0] = (dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2]) * A[n]

dp[n][1] = (dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2]) * B[n]

dp[n][2] = (dp[n - 1][0] + dp[n - 1][2]) * B[n - 1] + dp[n - 1][1] * (B[n - 1] - 1)

위와 같은 점화식으로 풀었습니다

dp[n][0] = n번째 난이도를 고정 난이도 문제에서 출제하는 경우의 수

dp[n][1] = n번째 난이도를 가변 난이도 문제중 i + 1 난이도에서 출제하는 경우의 수

dp[n][2] = n번째 난이도를 가변 난이도 문제중 i 난이도에서 출제하는 경우의 수

테스트 케이스와 제가 해본 몇개의 예제는 잘 작동합니다

혹시 어떤 반레가 있을까요?

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <string>
#include <queue>
#include <functional>
#include <time.h>
#include <set>

using namespace std;
const int mod = 1000000007;
int dp[100001][3];
int A[100001], B[100001];
int main() {
	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
	}
	for (int i = 1; i <= N - 1; i++) {
		scanf("%d", &B[i]);
	}
	dp[1][0] = A[1], dp[1][1] = B[1];
	for (int i = 2; i <= N; i++) {
		dp[i][0] = ((((dp[i - 1][0] + dp[i - 1][1])%mod + dp[i - 2][2]))%mod * A[i])%mod;
		dp[i][1] = ((((dp[i - 1][0] + dp[i - 1][1])%mod + dp[i - 2][2]))%mod * B[i])%mod;
		dp[i][2] = (((((dp[i - 1][0])%mod + dp[i - 1][2]))%mod * B[i - 1])%mod + dp[i - 1][1] * (B[i - 1] - 1))%mod;
	}

	printf("%d", ((dp[N][0] + dp[N][1])%mod + dp[N][2])%mod);
}

opalala 3달 전 0

dp[n][0] = n번째 난이도를 고정 난이도 문제에서 출제하는 경우의 수

dp[n][1] = n번째 난이도를 가변 난이도 문제중 i + 1 난이도에서 출제하는 경우의 수

dp[n][2] = n번째 난이도를 가변 난이도 문제중 i 난이도에서 출제하는 경우의 수

i +1 과 i 가 섞여서 출제된 경우가 있어요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2854번 문제 출제 질문입니다

pkc4913 4년 전 0

opalala 3달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말