3完とは言えそこそこいい結果だった回。
https://codeforces.com/contest/1456/problem/A
問題
01で構成された文字列Sと、整数P,Kが与えられる。
Sに対し以下を行える。
- コストXで、1か所0を1に変える。
- コストYで、先頭1文字を取り除く
最終的に、S[P+nK-1]がすべて1であるようにしたい。
最小コストを求めよ。
解法
先頭取り除く文字を総当たりしていけばよい。
K文字取り除く文字数を変えるたびに、コストXの数が1変わりうるので差分を更新していこう。
int T; int N,P,K,X,Y; string A; ll step[201010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>P>>K>>A; cin>>X>>Y; P--; FOR(i,2*N) step[i]=0; ll mi=1LL<<60; for(i=N-1;i>=P;i--) { step[i]=step[i+K]; if(A[i]=='0') step[i]+=X; mi=min(mi,1LL*Y*(i-P)+step[i]); } cout<<mi<<endl; } }
まとめ
解き味も問題設定もさほど面白く感じなかった…残念。