关于本题容易WA的几个点

混淆 $n$ 和 $m$ ， $n$ 是天数， $m$ 是点数，检查你计算 $cost[i][r]$ 时，枚举的是不是点数 $m$ ,还有 $cost[i][j] = d[m]$ 。

CPP

	for(int i=1; i<=n; i++)
	{
		for(int j=i; j<=n; j++)
		{
			memset(ok, 0, sizeof ok);
			for(int u=1; u<=m; u++)
				for(int k=i; k<=j; k++)
					if(limit[k][u])
					...
			spfa(1);
			cost[i][j] = d[m];
		}
	}

容易爆 $int$ 的地方:题中说每天都会有一条从 $1$ ~ $m$ 的路线，但是不保证第 $i$ ~ $j$ 天走同一条路能够到达，所以 $cost[i][j]$ 可能会等于 $INF$ ，所以和 $(i-j)$ 相乘就会爆掉，所以你可以采取下面这种写法来保证不会爆 $int$ ：

CPP

	for(int i=1; i<=n; i++)
	{
		f[i] = 2e9;
		for(int j=0; j<i; j++)
		{
			if(cost[j+1][i]!=INF)
				f[i] = min(f[i], f[j] + cost[j+1][i] * (i - j) + (!!j) * k);
		}
	}

关于为什么要 (!!j) * k,如果不这样的话，从

j=0

转移的话就会多加上

k

。

关于本题容易WA的几个点

讨论操作

回复

相关推荐

关于本题容易WA的几个点