求大神解答一个DP转移顺序的问题: 已经正确列出了转移方程,但(我看起来)等价的两种转移方程写法却得出了不同的结果。如下:
w=3*n-h+1;
OH y[s][g][j][k][l][p][q]=0;
OH
{
z=y[s^1][g][j][k][l][p][q];
if(c[h]=='1'||c[h]=='0')
{
if(g<n)J(y[s][g+1][j][k][l][p][q],z);
if(j>0&&p<n)J(y[s][g][j-1][k][l][p+1][q],z*j);
if(q>0)J(y[s][g][j][k][l][p][q-1],z*q);
}
if(c[h]=='2'||c[h]=='0')
{
if(j<n)J(y[s][g][j+1][k][l][p][q],z);
if(k>0&&q<n)J(y[s][g][j][k-1][l][p][q+1],z*k);
if(l>0)J(y[s][g][j][k][l-1][p][q],z*l);
}
if(c[h]=='3'||c[h]=='0')
{
if(k<n)J(y[s][g][j][k+1][l][p][q],z);
if(g>0&&l<n)J(y[s][g-1][j][k][l+1][p][q],z*g);
if(p>0)J(y[s][g][j][k][l][p-1][q],z*p);
}
}
s^=1;
w=3*n-h+1;
OH y[s][g][j][k][l][p][q]=0;
OH
{
int& z=y[s][g][j][k][l][p][q];
if(c[h]=='1'||c[h]=='0')
{
if(g>0)J(z,y[s^1][g-1][j][k][l][p][q]);
if(j<n&&p>0)J(z,(j+1)*y[s^1][g][j+1][k][l][p-1][q]);
if(q<n)J(z,(q+1)*y[s^1][g][j][k][l][p][q+1]);
}
if(c[h]=='2'||c[h]=='0')
{
if(j>0)J(z,y[s^1][g][j-1][k][l][p][q]);
if(k<n&&q>0)J(z,(k+1)*y[s^1][g][j][k+1][l][p][q-1]);
if(l<n)J(z,(l+1)*y[s^1][g][j][k][l+1][p][q]);
}
if(c[h]=='3'||c[h]=='0')
{
if(k>0)J(z,y[s^1][g][j][k-1][l][p][q]);
if(g<n&&l>0)J(z,(g+1)*y[s^1][g+1][j][k][l-1][p][q]);
if(p<n)J(z,(p+1)*y[s^1][g][j][k][l][p+1][q]);
}
}
s^=1;
OH为循环的简写,如下:
#define OH \
for(g=0;2*g<=w&&g<=n&&g<=h;g++)\
for(j=0;2*(g+j)<=w&&g+j<=n&&g+j<=h;j++)\
for(k=0;2*(g+j+k)<=w&&g+j+k<=n&&g+j+k<=h;k++)\
for(l=0;2*(g+j+k)+l<=w&&g+j+k+l<=n&&g+j+k+2*l<=h;l++)\
for(p=0;2*(g+j+k)+l+p<=w&&g+j+k+l+p<=n&&g+j+k+2*(l+p)<=h;p++)\
for(q=0;2*(g+j+k)+l+p+q<=w&&g+j+k+l+p+q<=n&&g+j+k+2*(l+p+q)<=h;q++)