読者です 読者をやめる 読者になる 読者になる

PKU 2431 Expedition

Programming Algorithm PKU

2431 -- Expedition

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
	int N;
	vector<pair<int, int> > v;
	scanf("%d\n", &N);
	for(int i = 0; i < N; i++){
		int x, y;
		scanf("%d %d\n", &x, &y);
		v.push_back(make_pair(x, y));
	}
	int L, P;
	scanf("%d %d\n", &L, &P);
	sort(v.begin(), v.end());
	vector<pair<int, int> >::reverse_iterator rit = v.rbegin();
	priority_queue<int> pq;
	int cnt = 0;
	while(L){
		if(L == (*rit).first){
			pq.push((*rit).second);
			rit++;
		}
		if(P == 0){
			if(pq.empty()){
				cnt = -1;
				break;
			}
			P += pq.top();
			pq.pop();
			cnt++;
		}
		P--;L--;
	}
	printf("%d\n", cnt);
	return 0;
}

関係ないが動的計画法が理解できない。耳で聞いて概念としては理解できるのだが、自分で実装してみたりできる所までは理解できず、結局なかなか手を出さないまま終了している。誰か僕にも実装ができるように教えてくれ