BOJ 1516-ゲーム開発

タイムアウトメモリ制限正解の発行正解正解正解正解正解率2秒128 MB 85584050321247.55%

質問する

同社は今回、新しい戦略シミュレーションゲームの3準ゲームを開発することにした.コア部分はすでに開発済みで、各種族のバランスやゲーム時間全体の調整などの部分しか残っていない.
ゲームに入る時間は状況によって異なる可能性があるため、すべての建物を建てるのに要する最小限の時間を利用して近似することにした.もちろん、問題は簡単ではないかもしれません.あるビルを建てるためには、まず別のビルを建てる必要があるかもしれません.例えば、星間争覇の中に砦を建てるためには、まず砦を建てるので、先に建ててから砦を建てる.複数の建物を同時に建てることができます.
便利な資源が無限に多いと仮定し、建物の建設命令を下すには時間がかからない.

入力

第1列目は、建物の種類数N(1≦N≦500)を与える.次のN行は、各建物を建てるのに要する時間と、その建物を建てるためにまず建てる建物の番号を示しています.建物の番号は1からNまでで、各行は-1で終わります.各建物を建てるのに要する時間は100000以下の自然数です.

しゅつりょく

N個の建物の完成に要する最小時間を出力します.

に近づく

すぐにトポロジーソフトの問題を考えましたが、
記録がはっきりしていれば、位相整列を行う必要はありません.
すなわち,Top-Down形式のDP問題を用いて解答しても,効率的にコードを記述することができる.
選手の建物を見ながら、最大値を見つければ、いつ建物が建てられるかがわかります.

に答える

並ぶ前に、選手たちの建物をキャリヤーとして入れます.
そして1からNまで巡回し、DFSに戻ればよい.
ans値が-1でない場合は、すぐに返されるコメントが重要になります.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, num, T[501], ans[501];
vector<int> before[501];

int DFS(int node)
{
	if (ans[node] != -1) return ans[node];
	int max_time = 0;
	for (int b : before[node])
	{
		max_time = max(max_time, DFS(b));
	}
	return ans[node] = T[node] + max_time;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	MS(ans, -1);
	CIN(N);
	FUP(i, 1, N)
	{
		CIN(T[i]);
		while(true)
		{
			CIN(num);
			if (num == -1) break;
			before[i].push_back(num);
		}
	}
	FUP(i, 1, N)
	{
		if(ans[i] == -1) DFS(i);
		COUT(ans[i]);
		ENDL;
	}

	return 0;
}