第12回 アルゴリズム実技検定 : M - シリーズ

これは割とすんなり。
https://atcoder.jp/contests/past202209-open/tasks/past202209_m

問題

N巻からなるのシリーズの本がある。

• i巻目を単独で買うのはA[i]円かかる。
• L[i]～R[i]巻目をセットで買うのはB[i]円かかる。

全巻を１冊以上買うのにかかる最小コストを求めよ。

解法

dp(n) := n巻目までそろえる最小コスト
とする。
前者の買い方も、i～i巻目セットを買うのにA[i]かかる、とみなすと両者同じようなものとみなすことができる。

dp(n)は、R[i]=nであるような買い方におけるmin(dp(L[i]-1)....dp(R[i])-1)+B[i]の最小値である。
これはdp(n)を区間最小値のSegTreeに乗せれば求めることができる。

int N,M;
vector<pair<int,int>> cand[202020];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1LL<<60;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		cand[i+1].push_back({i,x});
	}
	FOR(i,M) {
		cin>>x>>y>>k;
		cand[k].push_back({y-1,x});
	}
	st.update(0,0);
	
	for(i=1;i<=N;i++) {
		FORR2(a,b,cand[i]) {
			ll c=st.getval(a,i+1)+b;
			st.update(i,c);
		}
	}
	
	cout<<st.getval(N,N+1)<<endl;
}

まとめ

PASTのM問にしては易しめ？