首页 > ACM题库 > HDU-杭电 > HDU 1545 01-K Code-动态规划-[解题报告] C++
2013
12-12

HDU 1545 01-K Code-动态规划-[解题报告] C++

01-K Code

问题描述 :

Consider a code string S of N symbols, each symbol can only be 0 or 1. In any consecutive substring of S, the number of 0′s differs from the number of 1′s by at most K. How many such valid code strings S are there?

For example, when N is 4, and K is 3, there are two invalid codes: 0000 and 1111.

输入:

The input consists of several test cases. For each case, there are two positive integers N and K in a line.

N is in the range of [1, 62].

K is in the range of [2, 5].

输出:

Output the number of valid code strings in a line for each case.

样例输入:

1 2
4 3

样例输出:

2
14

http://acm.hdu.edu.cn/showproblem.php?pid=1545

const int MM = 11111;
#define debug puts("wrong")
typedef __int64 int64;
int N,M;
int64 dp[63][11][11];//j min(0-1) k max(0-1)

void solve() {
    int i,j,k;int64 tmp,t1,t2;
    memset(dp[0],0,sizeof(dp[0]));
    dp[0][M][M]=1;
    for(i=1;i<=N;i++) {
        memset(dp[i],0,sizeof(dp[i]));
        for(j=-M;j<=M;j++) {
            for(k=-M;k<=M;k++) {
                tmp=dp[i-1][j+M][k+M];
                if(tmp==0) continue;
                t1=f_min(j+1,1),t2=f_max(k+1,1);
                if(t1>=(-M) && t2<=M)dp[i][t1+M][t2+M]+=tmp; //0
                t1=f_min(j-1,-1),t2=f_max(k-1,-1);
                if(t1>=(-M) && t2<=M)dp[i][t1+M][t2+M]+=tmp; //1
            }
        }
    }
    int64 ans=0;
    for(i=-M;i<=M;i++) for(j=-M;j<=M;j++) {
        ans+=dp[N][i+M][j+M];
//        printf("%d %d %d\n",i,j,dp[2][i+M][j+M]);
    }
    printf("%I64d\n",ans);
}

 

解题报告转自:http://www.cnblogs.com/zhang1107/archive/2013/05/04/3058993.html