通った回数をカウントする

個人メモになります(僕が知らなかっただけ)

Markdownで画像が入らなかった; ;

JOI2014/2015 本選A 鉄道旅行 (Railroad Trip)

この問題は各駅何回通ったかを記録(visit[i])し

min(A[i] * visit[i],B[i] * visit[i] + C[i])

を足していけばいいのですが、駅を通る回数のカウントの仕方を知らなかったので記録しておきます

無向グラフなので小さい方から大きい方に向かうとします

するとこのように考えられます

ここで辺の数が増減するポイントに+1,-1を記録していくことで

visitが調べられます

cin >> P[0];
P[0]--;
for(int i = 1;i < M;i++)
{
	cin >> P[i];
	P[i]--;
	int from = min(P[i - 1],P[i]);
	int to = max(P[i - 1],P[i]);
    //始まるところに+1
	visit[from] += 1;
    //最後に訪れる点の次の点に-1
	visit[to] -= 1;
}
for(int i = 1;i < N - 1;i++)
{
    //足していく
	visit[i] += visit[i - 1];
}

メモ終わり!

追記 imos法だそうです...知らなかった...