$dp[i][j][k]=i$ 번째 문자까지 봤을 때 변경을 사용했는지 여부 $k(=0 \ \text{or}\ 1)$, 그리고 지금까지 만난 가장 큰 수가 $j(A \le j \le E)$ 일 때 최대값
으로 정의한다.
현재 $dp[i][j][k]$ 일 때, 현재 문자를 그대로 냅둘 수 있고, 혹은 $k=0$ 이라면 바꿀 수도 있다.
Greedy
놀랍게도 각 $A \sim E$ 에 대해 처음 나오는 위치와 끝나는 위치 최대 $10$ 개에 대해서만 다른 문자로 바꿀지 말지를 고려해주면 된다.
총 50가지 경우가 되고 $O(50n)$ 으로 풀 수 있다고 한다.
만약 문자를 더 크게 만드는 경우라면 이게 커져서 + 였다가 - 가 되는 문자들이 생긴다.
이런 문자는 최대한 적게 생기는게 좋기 때문에 가장 빨리 있는것을 바꾸는게 최적이 될 것이다.
문자를 더 작게 만드는 경우도 동일하다.
Prefix sum
내가 푼 방법인데, 난 실제 모든 자리의 모든 문자들을 바꿔 직접 값을 계산했다.
예를들어 문자를 더 크게 만드는 경우엔 + 였다가 - 가 되는 문자의 개수를 셌다.
각 문자가 나오는 인덱스를 관리하면 이것이 가능한데 복잡해서 코드만 투척한다.
intval(inti){if(i==0)return1;if(i==1)return10;if(i==2)return100;if(i==3)return1000;if(i==4)return10000;}voidsolve(){strings;cin>>s;intn=sz(s);vvipsum(5,vi(n+1));viosum(n+1);vviidx(5);for(inti=0;i<n;i++)idx[s[i]-'A'].pb(i);for(inti=0;i<n;i++){for(intj=0;j<5;j++){psum[j][i+1]=psum[j][i]+(s[i]-'A'==j);}osum[i+1]=osum[i]+val(s[i]-'A');}autoqry=[&](intk,intl,intr){if(l>r)return0ll;returnpsum[k][r+1]-psum[k][l];};intcur_max=-1;intans=0;for(inti=n-1;i>=0;i--){if(s[i]-'A'<cur_max)ans-=val(s[i]-'A');elseans+=val(s[i]-'A');maxa(cur_max,int(s[i]-'A'));}debug(ans);cur_max=-1;intoans=ans;// CDDEfor(inti=n-1;i>=0;i--){intcur=s[i]-'A';idx[cur].pop_back();for(intto=4;to>=0;to--){inttmp=oans;if(cur==to)continue;tmp-=val(cur)*(cur_max>cur?-1:1);tmp+=val(to)*(cur_max>to?-1:1);if(to<cur){// 더 작아진다면// 4 -> 3 이 된다면// 2 3 3 4intlidx=0;if(sz(idx[cur]))lidx=idx[cur].back();for(intk=cur-1;k>=to;k--){if(cur_max>k){}else{// 원래 - 였다가 + 가 되는 것의 수intbigger=0;bigger=qry(k,lidx,i-1);tmp+=bigger*val(k)*2;}if(sz(idx[k]))maxa(lidx,idx[k].back());}}else{// 더 커진다면// 2 -> 4 가 된다고 하자.// 4 2 3 4intlidx=0;if(sz(idx[to]))lidx=idx[to].back();//if (sz(idx[cur])) lidx = idx[cur].back();for(intk=to-1;k>=cur;k--){if(cur_max>k){}else{// 원래 + 였다가 - 가 되는 것의 수intsmaller=0;smaller=qry(k,lidx,i-1);tmp-=smaller*val(k)*2;}if(sz(idx[k]))maxa(lidx,idx[k].back());}}maxa(ans,tmp);}maxa(cur_max,cur);}cout<<ans<<endl;}
왜냐면 segment가 하나 사용될 때마다 그것의 길이가 $L$ 이라면 $L-1$ 의 정답을 얻기 때문이다.
최악의 경우 최대 $O(n^2)$ 개의 segment가 생기기 때문에 압축된 형태로 저장하며 값을 계산해야 한다.
matrix를 위에서 아래로 보면 검은색이 끝날 때마다 segment들이 merge된다.
그런데 이걸 계속 모두 관리하는건 결국 $O(n^2)$ 라서 불가능하다.
현재 row가 $y$라고 하면 $a_i=y$ 인 $i$ 들만 고려한다.
어떠한 segment의 시작과 끝이 $l, r$ 이라면 현재 matrix에서의 row를 $y$라고 할 때 $ey=\text{Min}(a_{l-1}, a_{r+1})$ 이 그 다음 구간으로 확장되는 시점이다. 따라서 그걸 $r-l+1$ 길이의 segment를 $ey-y$ 개 얻었다고 볼 수 있다.
이런식으로 얻게되는 길이를 모두 카운트해둔다음에 큰 길이의 segment부터 $m$이 다 없어지거나 segment를 다 쓸 때 까지 정답에 더해주면 된다.
structDSU{vector<int>p,l,r;DSU(intn):p(n,-1),l(n),r(n){iota(all(l),0);iota(all(r),0);}intgp(intn){if(p[n]<0)returnn;returnp[n]=gp(p[n]);}voidmerge(inta,intb,intto_b=1){a=gp(a),b=gp(b);if(a==b)return;if(!to_b&&size(a)>size(b))swap(a,b);p[b]+=p[a];mina(l[b],l[a]);maxa(r[b],r[a]);p[a]=b;}boolis_merged(inta,intb){returngp(a)==gp(b);}intsize(intn){return-p[gp(n)];}};voidsolvee(){intn;llm;cin>>n;// column 에서 0 ~ a[i]-1 은 검은색 a[i] ~ n -1 은 흰색// 하나의 row에서 white로만 이루어진 연속된 구간들의 길이를 모두 구해야한다.// 연속된 구간의 길이가 k면 k - 1 개의 점수를 획득하고 k 개의 숫자를 소모한다.// 만약 k = 1 라면 행동을 취하지 않는다.via(n);fv(a);cin>>m;viidx(n);iota(all(idx),0);sort(all(idx),[&](inti,intj){returna[i]<a[j];});llans=0;vialive(n);DSUdsu(n);viseg_cnt(n+1);for(inty=0,j=0;y<n;y++){viused;while(j<n&&a[idx[j]]<=y){alive[idx[j]]=1;if(idx[j]!=0&&alive[idx[j]-1]){dsu.merge(idx[j]-1,idx[j]);}if(idx[j]!=n-1&&alive[idx[j]+1]){dsu.merge(idx[j]+1,idx[j]);}used.pb(idx[j]);j++;}vinxt;for(intj:used){if(j==dsu.gp(j)){nxt.pb(j);intlen=dsu.r[j]-dsu.l[j]+1;intnxt_merge=n;intL=dsu.l[j],R=dsu.r[j];if(L!=0)mina(nxt_merge,a[L-1]);if(R!=n-1)mina(nxt_merge,a[R+1]);intadded=nxt_merge-y;seg_cnt[len]+=added;}}}debug(seg_cnt);for(inti=n;i>=2;i--){lllen=i;llq=min<ll>(seg_cnt[i],m/len);seg_cnt[i]-=q;m-=q*len;ans+=(len-1)*q;while(m>1&&seg_cnt[i]--){lladded=min<ll>(m,len);m-=added;ans+=max(0ll,added-1);}}cout<<ans<<endl;}
Comments