Bug:

【原始代码】

Pf[u][0] = Pc[u][0] = 0;
fortodo(i, 1, ecnt)
	{
		incre = max(dp[Es[u][i]][0], dp[Es[u][i]][2]);
		Pf[u][i] = Pf[u][i - 1] + incre;
		Pc[u][i] = max(Pc[u][i - 1] + incre, Pf[u][i - 1] + dp[Es[u][i]][1]);
	}
Sf[u][ecnt + 1] = Sf[u][ecnt + 1] = 0;
for (i = ecnt; i; i--)
	{
		incre = max(dp[Es[u][i]][0], dp[Es[u][i]][2]);
		Sf[u][i] = Sf[u][i + 1] + incre;
		Sc[u][i] = max(Sc[u][i + 1] + incre, Sf[u][i + 1] + dp[Es[u][i]][1]);
	}
Alclear[u] = true;

int trk = erk[u].find(ie)->second;
dp[ce][0] = Pf[u][trk - 1] + Sf[u][trk + 1];
dp[ce][1] = e[ce][2] + dp[ce][0];
dp[ce][2] = max(Pc[u][trk - 1] + Sf[u][trk + 1], Pf[u][trk - 1] + Sc[u][trk + 1]);

【AC代码】

Pf[u][0] = 0;
Pc[u][0] = -INF;
fortodo(i, 1, ecnt)
	{
		incre = max(dp[Es[u][i]][0], dp[Es[u][i]][2]);
		Pf[u][i] = Pf[u][i - 1] + incre;
		Pc[u][i] = max(Pc[u][i - 1] + incre, Pf[u][i - 1] + dp[Es[u][i]][1]);
	}
Sf[u][ecnt + 1] = 0;
Sc[u][ecnt + 1] = -INF;
for (i = ecnt; i; i--)
	{
		incre = max(dp[Es[u][i]][0], dp[Es[u][i]][2]);
		Sf[u][i] = Sf[u][i + 1] + incre;
		Sc[u][i] = max(Sc[u][i + 1] + incre, Sf[u][i + 1] + dp[Es[u][i]][1]);
	}
Alclear[u] = true;

int trk = erk[u].find(ie)->second;
dp[ce][0] = Pf[u][trk - 1] + Sf[u][trk + 1];
dp[ce][1] = e[ce][2] + dp[ce][0];
if (Es[u].size() > 2)
	dp[ce][2] = max(Pc[u][trk - 1] + Sf[u][trk + 1], Pf[u][trk - 1] + Sc[u][trk + 1]) + e[ce][2];
else	
	dp[ce][2] = -INF;

总之就是没有讨论dp[][2]的Impossible情形……
足足又调了一个小时+想一晚上……sigh……

• 相关文章
• 全局相关文章