【解题报告】[动态规划] RQNOJ - PID105 / 核电站问题

原题地址：http://www.rqnoj.cn/problem/105

解题思路：

　　状态表示：

　　　　数组dp[i][j]中的j拆成M位二进制（后缀B表示）。

　　　　如：M=3时

　　　　dp[5][000B]表示第3,4,5都不放核物质的情况的总数。显然，dp[5][000B]=dp[5][001B]=dp[4][000B]+dp[4][100B]。特殊的是dp[i][111B]=0。

　　初始状态：

　　　　dp[0][000B]=dp[0][001B]=1，dp[0][i]=0（001B<i<=111B）

　　状态转移方程：

　　　　dp[i][j]=dp[i-1][ (j>>1) + (1<<(N-1)) ]+dp[i-1][j>>1]。 0<=j<((1<<n)-1)

解题代码：

 #include<stdio.h>

 #include<iostream>

 using namespace std;

 long long dp[][]={,};

 int main()

 {

     long long n,m,i,j;

     scanf("%lld%lld",&n,&m);

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

     {

         for(j=;j<((<<m)-);j++)

         {

             dp[i][j]=dp[i-][(j>>1LL)+(<<(m-1LL))]+dp[i-][j>>1LL];

         }

     }

     i--;

     long long s=;

     for(j=;j<((<<m)-);j++)

     {

         s+=dp[i][j];

     }

     printf("%lld\n",s);

     return ;

 }

巴特西

【解题报告】[动态规划] RQNOJ - PID105 / 核电站问题

最新文章

热门文章