DP 물 문제

1289 단어 dp
가설의 자연수 N의 K 랜덤 바이너리는 서로 인접하지 않은 두 개의 인접한 숫자를 나타낸다.그럼 이 숫자가 K가 낫다고 할까요?
L지점 K16진수 K의 상당수를 구걸하다.
예를 들어 K = 4.언제?전체 K가 낫다 11, 13, 20, 22, 30, 31, 33 모두 7개.이 숫자는 매우 크기 때문에, 1000000007의 값을 출력하십시오.
약간 디지털 DP 냄새가 나요. 이거는 서로 인접하지 않지만 자신과 할 수 있어요.
그리고 매거진은 앞으로 꽂는 거예요.
dp[i][j]가 i로 길고 j가 앞장서는 개수.
또 약간의 미루는 냄새가 난다.
#include<algorithm>
#include<iostream>
#include<iterator>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<map>
#define mem(a) memset(a,0,sizeof(a))
#define inf (1<<30)
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn=10+100;

ll dp[20][20];
int main()
{
    int k,l;
    scanf("%d%d",&k,&l);
    for(int i=0;i<k;i++) dp[1][i]=1;
    for(int i=2;i<=l;i++)
        for(int j=1;j<k;j++)
        {
            dp[i][j]=dp[i-1][j];
            for(int m=0;m<j-1;m++)
                dp[i][j]+=dp[i-1][m];
            for(int m=j+2;m<k;m++)
                dp[i][j]+=dp[i-1][m];
            dp[i][j]%=mod;
        }

    ll ans=0;
    for(int i=1;i<k;i++)
        ans+=dp[l][i];
    if(k<=2) ans=0;
    cout<<ans<<endl;
    return 0;
}

판권 성명: 본 블로그의 오리지널 글, 블로그는 동의 없이 전재할 수 없습니다.

좋은 웹페이지 즐겨찾기