Kodamanと愉快な仲間たち : Q - TAPIX

ここらへんもまだ簡単。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/tapix

問題

N人の生徒とM人の先生がおり、各生徒に対し、志望校合格までに必要な学力の上昇量と、ついている先生の情報が与えられる。
先生1人に1円支払うと、その先生に教わっている生徒全員の学力が1上がる。
全体でK人志望校に合格させるのに必要な最低金額を求めよ。

解法

各先生に対し、その先生につく生徒の必要学力上昇量を昇順で並べれば、何名合格させるのにいくらかかるかがわかる。
あとはK人合格させる最小コストを求めればよく、これはO(N^2+M)のDPで済む。

int N,M,X,K;
int P[5050];
vector<int> V[5050];

ll dp[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>X>>K;
	FOR(i,X) cin>>P[i];
	FOR(i,N) {
		cin>>x>>y>>j;
		V[j-1].push_back(max(0,P[x-1]-y));
	}
	FOR(i,N+1) dp[i]=1LL<<60;
	dp[0]=0;
	FOR(i,M) if(V[i].size()) {
		sort(ALL(V[i]));
		for(x=N;x>=0;x--) if(dp[x]<1LL<<60) {
			for(y=1;y<=V[i].size()&&x+y<=N;y++) dp[x+y]=min(dp[x+y],dp[x]+V[i][y-1]);
		}
	}
	
	cout<<dp[K]<<endl;
	
	
}

まとめ

まだ割と簡単だね。