| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 544866 | Deepesson | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MAX 405
///Uma dp meio complicadinha
///A ideia eh a seguinte:
///1-> Quantos valores azuis restam
///2-> Quantos valores vermelhos restam
///3-> Quantos valores verdes restam
///4-> (Para remover) coordenada atual
///Por enquanto sera O(N^4), mas poderemos otimizar depois
bool existe[4][MAX][MAX][MAX][4];
int tab[3][MAX][MAX][MAX][4];
std::vector<int> cords[3];
int N;
int array[MAX]={};
int getval(char ch){
if(ch=='R')return 0;else if(ch=='G')return 1;return 2;
}
int proximo(int red,int blue,int green){
int min=N;
if(red!=cords[0].size())min=std::min(min,cords[0][red]);
if(green!=cords[1].size())min=std::min(min,cords[1][green]);
if(blue!=cords[2].size())min=std::min(min,cords[2][blue]);
return min;
}
int dp(int val,int red,int blue,int green,int last){
if(red+blue+green==N)return 0;
int pos=0;
{
int arr[]={red,green,blue};
pos=cords[val][arr[val]];
}
if(existe[val][red][blue][green][last])return tab[val][red][blue][green][last];
existe[val][red][blue][green][last]=true;
///Prossegue com o valor
int ans=1e9;
if(array[pos]!=last){
switch(array[pos]){
case 0:
ans=dp(array[proximo(red+1,blue,green)],red+1,blue,green,array[pos]);break;
case 1:
ans=dp(array[proximo(red,blue,green+1)],red,blue,green+1,array[pos]);break;
case 2:
ans=dp(array[proximo(red,blue+1,green)],red,blue+1,green,array[pos]);break;
}
}
///O valor da distancia estah INCORRETO, como melhorar a conta?
///Faz a troca magica
if(last!=0&&red!=cords[0].size()&&array[pos]!=0){
int truecusto=0;
int destino = cords[0][red];
for(int i=0;i!=red;++i)if(cords[0][i]>=pos&&cords[0][i]<=destino)++truecusto;
for(int i=0;i!=green;++i)if(cords[1][i]>=pos&&cords[1][i]<=destino)++truecusto;
for(int i=0;i!=blue;++i)if(cords[2][i]>=pos&&cords[2][i]<=destino)++truecusto;
ans=std::min(ans,cords[0][red]-pos-truecusto + (dp(val,red+1,blue,green,0)));
}
if(last!=1&&green!=cords[1].size()&&array[pos]!=1){
int truecusto=0;
int destino = cords[1][green];
for(int i=0;i!=red;++i)if(cords[0][i]>=pos&&cords[0][i]<=destino)++truecusto;
for(int i=0;i!=green;++i)if(cords[1][i]>=pos&&cords[1][i]<=destino)++truecusto;
for(int i=0;i!=blue;++i)if(cords[2][i]>=pos&&cords[2][i]<=destino)++truecusto;
ans=std::min(ans,cords[1][green]-pos-truecusto + (dp(val,red,blue,green+1,1)));
}
if(last!=2&&blue!=cords[2].size()&&array[pos]!=2){
int truecusto=0;
int destino = cords[2][blue];
for(int i=0;i!=red;++i)if(cords[0][i]>=pos&&cords[0][i]<=destino)++truecusto;
for(int i=0;i!=green;++i)if(cords[1][i]>=pos&&cords[1][i]<=destino)++truecusto;
for(int i=0;i!=blue;++i)if(cords[2][i]>=pos&&cords[2][i]<=destino)++truecusto;
ans=std::min(ans,cords[2][blue]-pos-truecusto + (dp(val,red,blue+1,green,2)));
}
return tab[val][red][blue][green][last]=ans;
}
int main()
{
std::cin>>N;
std::string s;
std::cin>>s;
for(int i=0;i!=s.size();++i){
int u = getval(s[i]);
cords[u].push_back(i);
array[i]=u;
}
int ans=dp(array[0],0,0,0,3);
if(ans==1e9)ans=-1;
std::cout<<ans<<"\n";
}