PKU 3265 Problem Solving

• 何日目にどの問題を解いているかというDPです
• この解答ではダイクストラ法チックに解いています

int B[512];
int A[512];
int Bs[512][512];
int As[512][512];
int main()
{
	int M, P;
	cin >> M >> P;
	for (int i = 0; i < P; ++i) {
		cin >> B[i] >> A[i];
	}
	memset(Bs, 0, sizeof(Bs));
	memset(As, 0, sizeof(As));

	for (int i = 0; i < P; ++i) {
		for (int j = i + 1; j <= P; ++j) {
			As[i][j] = As[i][j - 1] + A[j - 1];
			Bs[i][j] = Bs[i][j - 1] + B[j - 1];
		}
	}

	vector<vector<int> > dp(P + 1, vector<int>(P + 1, INT_MAX / 2));
	dp[0][0] = 1;
	deque<pair<int, int> > q;
	q.push_back(make_pair(0, 0));
	while (!q.empty()) {
		const int from = q.front().first;
		const int to = q.front().second;
		q.pop_front();
		int cost = As[from][to];
		for (int i = to; i <= P && cost <= M; ++i) {
			if (dp[to][i] > dp[from][to] + 1) {
				q.push_back(make_pair(to, i));
				dp[to][i] = dp[from][to] + 1;
			}
			cost += B[i];
		}
	}
	cout << dp[P][P] << endl;
}