两种DP转移有什么不同?
查看原帖
两种DP转移有什么不同?
617078
zhouyuxuan3501楼主2024/7/17 19:21

求大神解答一个DP转移顺序的问题: 已经正确列出了转移方程,但(我看起来)等价的两种转移方程写法却得出了不同的结果。如下:

100分的代码。

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;

50分的代码。

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++)
2024/7/17 19:21
加载中...