yukicoder : No.3424 Shooting Game

これは割と素直な問題。
https://yukicoder.me/problems/no/3424

問題

N個の的があり、i個目の的は時刻L[i]～R[i]の間し、撃つとP[i]のスコアを得られる。
今持っている銃は１発で１個の的を撃つことが出来、一度弾を撃つと次に撃つまでT秒以上待つ必要がある。
なお、各的の出現時間はT秒未満である。

得られる総スコアの最大値を求めよ。

解法

各的の出現時間はT秒未満なので、撃つタイミングを決めたら、撃つ的はその時出現している最多スコアのもの一択である。
各タイミングでの最多スコアの的は、時刻にそって平面走査すればよい。
f(t) := 時刻tで撃てる的の最大スコア
dp(t) := 時刻tまでに得られる最大総スコア

とするとdp(t) = max(dp(t-1), dp(t-T)+f(t-T))となる。
あとはDPでdp(t)を順次求めて行くだけ。

int N,T;
vector<int> add[402020],del[402020];
ll dp[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) {
		cin>>x>>y>>k;
		add[x].push_back(k);
		del[y].push_back(k);
	}
	multiset<int> C;
	FOR(i,401010) {
		dp[i+1]=max(dp[i],dp[i+1]);
		FORR(a,add[i]) C.insert(a);
		
		if(C.size()) dp[i+T]=max(dp[i+T],dp[i]+*C.rbegin());
		FORR(a,del[i]) C.erase(C.find(a));
	}
	
	cout<<dp[401010]<<endl;
	
}

まとめ

割とすんなり。