Lflame

【2016/3/1 考题】 B题 动态规划

    题意：有 N 根(N<=1000)火柴，要拼出 a - b = c 的形式(减号与等号需要火柴)，问方案数。

    这种类型的DP需要多写写。

    首先，N 减去等号和减号需要的火柴数。然后转化一下形式，转为现在要拼出 c = a + b 的方案数。

    考虑从高位到低位一位一位地填，且是 a、b、c 同时填。

    那么 dp[i][j][k1][k2] 为还剩 i 根火柴，j 表示 c 当前位是否需要进位(即大于9)，k1表示 a 是否前面填的全是0，k2表示 b 是否前面填的全是0。

    k1和k2是来判断如果 a 或 b 这一位填 0，是否需要消耗火柴。

    然后枚举填哪个数字转移就好。

    注意，DP状态中并没有存储当前的位数，因为其实位数是不需要存的，只需要存火柴剩余数即可。

    

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

//首先将问题转化为 c=a+b

int n,MOD ;

int A[10]={6,2,5,5,4,5,6,3,7,6};

int dp[1005][2][2][2] ;  //还剩 i 根火柴  j表示是否需要进位  k1表示a是否前面全是0  k2表示b是否前面全是0

void update(int i,int j,int k1,int k2)  //更新别的状态

{

for(int num_c=0;num_c<=9;++num_c){  //枚举c当前位的数字

if(i==n && !num_c)continue ;

for(int n_j=0;n_j<2;++n_j){

bool t=0 ; int num=num_c-n_j ;

if(num<0) num=9 , t=true ;

if(t && !j)continue ;

for(int num_a=0;num_a<=9;++num_a){

int num_b; 

if(j && !t)num_b=num+10-num_a ;

elsenum_b=num-num_a ;

if(num_b<0||num_b>9)continue ;

int costs=((num_a==0&&k1)?0:A[num_a])+((num_b==0&&k2)?0:A[num_b])+A[num_c] ;

int n_k1=0,n_k2=0 ;

if(num_a==0 && k1)n_k1=true ;   if(num_b==0 && k2)  n_k2=true ;

if(costs<=i)dp[i-costs][n_j][n_k1][n_k2]=(int)(((long long)dp[i-costs][n_j][n_k1][n_k2]+dp[i][j][k1][k2])%MOD) ;

}

}

}

}

int main()

{

freopen("A.in","r",stdin) ;

scanf("%d%d",&n,&MOD) ;

n-=3 ;

dp[n][0][1][1]=1 ;

for(int i=n;i>0;--i){

for(int j=0;j<2;++j){

for(int k1=0;k1<2;++k1){

for(int k2=0;k2<2;++k2){

if(!dp[i][j][k1][k2])continue ;

update(i,j,k1,k2) ;

}

}

}

}

printf("%d\n",dp[0][0][0][0]) ;

return 0 ;

}