HDU 5642 King's Order 디지털 dp

1086 단어
제목: n 길이의 문자열로 같은 자모를 연속으로 세 번 초과할 수 없습니다. 몇 가지 조합 방식이 있는지 물어보세요.
생각: dp[a][b], 현재 a위, 앞에 연속적으로 같은 a개를 더하면 모두 b개, 이때 dp[a][b]종이 가능하다.dp[0][1]=26을 초기화하면 첫 번째 자리와 두 번째 자리의 세 번째 자리를 마음대로 놓을 수 있다.
b=2, 3시 분명히 그들은 마음대로 놓을 수 있기 때문에 그의 가능성은 dp[a-1][b]%mod일 수도 있다.그가 앞과 똑같이 놓아야 하기 때문에, 당연히 가능한 개수는 변하지 않을 것이다.
b=1일 때 분명히 그의 앞에 있는 하나는 연속적으로 같고 두 개는 같고 세 개는 같지만 그는 앞에 있는 것과 같지 않다. 그래서 그의 가능성 개수는 (dp[a-1][1]+dp[a-1][2]+dp[a-1][2]+dp[a-1][3])*25이다.
여기.×25는 이것이 반드시 이전과 같지 않다는 것을 나타낸다.
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const __int64 mod=1e9+7;
__int64 dp[2005][4];
int main()
{
    int test;
    dp[0][1]=26;
    for(int i=1;i<=2000;i++)
    {
        dp[i][2]=dp[i-1][1]%mod;
        dp[i][3]=dp[i-1][2]%mod;
        dp[i][1]=(dp[i-1][1]+dp[i-1][2]+dp[i-1][3])%mod*25;
    }
    scanf("%d",&test);
    while(test--)
    {
        int n;
        scanf("%d",&n);
        printf("%I64d
",(dp[n-1][1]+dp[n-1][2]+dp[n-1][3])%mod); } return 0; }

좋은 웹페이지 즐겨찾기