CCF 연습문제 201312-4 재미있는 숫자(DP)
아이디어:
DP 사상!
이렇게 생각하면 2차원 dp[i][j]를 설계할 수 있다. i는 현재 i개수를 채우고 이때는 j개 상태이다!
1차원은 말할 것도 없고, 2차원을 말해 봐!
총 4개의 수가 있습니다. 0, 1, 2, 3. 그러면 현재 i개의 수를 채워야 할 때, 이때 이미 몇 개의 수를 채웠고, 아직 채우지 않은 수가 남았습니다. 이 채운 수의 집합은 상태입니다!
0,1,2,3의 네 개의 수는 모두 0,1,2,3,01,02,03,12,13,2301201302312301230123012323이 있습니다. 생각해 보면 요구에 부합되는 상태는 6개밖에 없습니다!
각각:
2,02,23,012,023,0123
그래서 2차원은 6개만 세면 돼!
상태를 예로 들자.
예를 들어 이 상태가 023이라면 이동은 02에 3을 더해서 할 수도 있고 23에 0을 더해서 할 수도 있고 023에 0을 더하거나 3을 더해서 할 수도 있다!
따라서 [4]=[1]*1+[2]*1+[4]*2;
모형을 잘 취하면 됩니다!
구덩이:
비록 모형을 뽑았지만, 여전히 int가 터질 것이다
롱롱 하면 돼!
코드 참조:
#include
#include
#include
using namespace std;
const int mod = 1000000007;
const int maxn = 1000 + 10;
typedef long long ll;
ll dp[maxn][7];
int main(){
int n;
scanf("%d",&n);
for (int i = 1; i <= n; ++i){
dp[i][0] = 1;
dp[i][1] = (dp[i-1][0] % mod + (dp[i-1][1]%mod) * 2) % mod;
dp[i][2] = (dp[i-1][0] % mod + dp[i-1][2] % mod) % mod;
dp[i][3] = (dp[i-1][1] % mod + (dp[i-1][3] % mod) * 2) % mod;
dp[i][4] = (dp[i-1][1]%mod + dp[i-1][2]%mod + (dp[i-1][4]%mod) * 2) % mod;
dp[i][5] = (dp[i-1][3] % mod + dp[i-1][4] % mod + (dp[i-1][5] % mod) * 2) % mod;
}
printf("%lld
",dp[n][5] % mod);
return 0;
} 문제 설명
시험 문제 번호:
201312-4
시험 제목:
재미있는 수
시간 제한:
1.0s
메모리 제한:
256.0MB
문제 설명:
문제 설명
우리는 하나의 수를 흥미롭다고 하는데, 단지 다음과 같다.
1. 그것의 숫자는 0, 1, 2, 3만 포함되며, 이 네 개의 숫자는 적어도 한 번은 나타났다.
2. 모든 0은 모든 1 앞에 나타나고, 모든 2는 모든 3 앞에 나타난다.
3. 가장 높은 숫자는 0이 아니다.
따라서 우리가 정의한 가장 작은 흥미로운 수는 2013이다.이외에도 4명의 흥미로운 수는 2031과 2301이다.
마침 n자리가 있는 재미있는 수의 개수를 계산해 주세요.답안이 매우 클 수 있으므로, 답안을 1000000007의 나머지로 출력하기만 하면 된다.
입력 형식
올바른 정수 n(4≤n≤1000)을 포함하여 한 줄만 입력합니다.
출력 형식
출력은 n자리의 정수 중 재미있는 수를 포함하는 개수를 1000000007의 나머지로 나누는 한 줄만 있습니다.
샘플 입력
4
샘플 출력
3
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
