yukicoder : No.2139 K Consecutive Sushi

これは典型かな。
https://yukicoder.me/problems/no/2139

問題

N個の寿司が並んでおり、それぞれのおいしさA[i]が与えられる。
ここからいくつか寿司を食べるが、K個以上連続した寿司を食べてはいけない。
その条件を満たす範囲で、食べる寿司のおいしさの総和を最大化せよ。

解法

食べた美味しさの総和の最大化ではなく、食べない寿司のおいしさの総和の最小化を目指そう。
f(n) := 先頭から見て、n個目を食べないようにした場合の、そこまでの食べなかった寿司のおいしさの総和の最小値
とすると、
f(n) = A[i] + min(f(n-1),f(n-2),...,f(n-K))
とするのが先。これはSegTreeやSliding Windowで容易に計算できる。

int N,K;
ll A[202020],S[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]=v; //上書きかチェック
		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>>K;
	st.update(0,0);
	ll sum=0;
	ll ret=1LL<<60;;
	for(i=1;i<=N+1;i++) {
		if(i<=N) {
			cin>>A[i];
			sum+=A[i];
		}
		
		ll ma=st.getval(max(0,i-K),i)+A[i];
		if(i==N+1) {
			cout<<sum-ma<<endl;
			return;
		}
		st.update(i,ma);
	}
}

まとめ

これは易しめの★3な気はする。