2013 GDCPC J. Boring sequence

제목은 말할 것도 없고, 소가 보는 물문제는 내가 기다리는 물들은 생각지도 못했다...
코드를 직접 붙이면 최적화된 면이 완전히 없어...나중에 다른 테스트는 없고 문제 중의 몇 가지 사례와 1000999 같은 것만 테스트했습니다. 코드가 완전히 정확하다는 것을 보장할 수 없습니다.

/*

 *    dp[i][j][0]    i j 0       

 *     

 * dp[i][1][0]=sum(dp[i][k][1])(1<=k&&k<=K)

 *      dp[i][j]=dp[i-1][j-1],               

 *   2        ，     

 *   dp[i][j][0]==dp[i][j][1],  dp[i][1]  

 *       

 *      ans dp[n+1]      ，     

 */

#include <iostream>

using namespace std;



const int MOD=1007;

const int maxn=1002;

int dp[maxn]={2,2};

int b[maxn]={0,1};



int main()

{

//  freopen("in.txt","r",stdin);

    for(int i=2;i<maxn;i++)

        b[i]=(b[i-1]*2) % MOD;



    int n,K;

    while(~scanf("%d%d",&n,&K))

    {

        n++;

        for(int i=2;i<=n;i++)

        {

            dp[i]=0;

            for(int k=1;k<=i-1&&k<=K;k++)

                dp[i]=(dp[i]+dp[i-k])%MOD;

        }

        printf("%d
",(b[n]-dp[n]+MOD)%MOD);

    }

}

최적화된 코드로 구상된 생각: d[i]를 연속적으로 같은 문자의 길이가 K를 초과하지 않는 01 문자열의 개수로 정의하면 d[i]는 다음과 같이 나눌 수 있다.
d[i-1]: 마지막 문자가 0이면 1을 추가하고 1을 추가하면 0을 추가합니다.
d[i-2]: 마지막 문자가 0이면 1 2개를 추가하고 1이면 0 2개를 추가합니다.
     ...
d[i-k]: 마지막 문자가 0이면 k개 1을 추가하고 반대로 1을 추가하면 k개 0을 추가합니다.
즉 d[i]=sum(d[j])(max(1,i-k)<=j<=i-1)
01열의 문제는 기본적으로 마지막부터 미루고 누적된다.최적화 방식에는 빠른 幂 등이 있다.
예전에 항저우 전기 2604와 비슷한데 전에 쓴 문제풀이 보고서를 봤어요. http://www.cnblogs.com/IT-BOY/archive/2013/02/03/2890841.html