제출 #137488

#제출 시각아이디문제언어결과실행 시간메모리
137488gs14004Vim (BOI13_vim)C++17
100 / 100
175 ms34920 KiB
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 70005;

int n;
char str[MAXN], buf[MAXN];
int chk[MAXN];
int dp[MAXN][10];
int d2[MAXN][10][10];

int f(int v, int w);
int g(int v, int win, int wout);

int g(int v, int win, int wout){
	if(v == n - 1) return 1e9;
	if(~d2[v][win][wout]) return d2[v][win][wout];
	int ret = 1e9;
	if(win + 'a' == str[v + 1] && wout + 'a' == str[v + 1]){
		for(int i=0; i<10; i++){
			ret = min(ret, f(v + 1, i) + 3);
		}
		for(int i=0; i<10; i++){
			for(int j=0; j<10; j++){
				ret = min(ret, g(v + 1, i, j) + 5);
			}
		}
	}
	else if(win + 'a' == str[v + 1]){
		for(int i=0; i<10; i++){
			ret = min(ret, g(v + 1, i, wout) + 3);
		}
		ret = min(ret, f(v + 1, wout) + 1);
	}
	else if(wout + 'a' == str[v + 1]){
		for(int i=0; i<10; i++){
			ret = min(ret, g(v + 1, win, i) + 3);
		}
	}
	else{
		ret = min(ret, g(v + 1, win, wout) + 1);
	}
	return d2[v][win][wout] = ret;
}

int f(int v, int w){
	if(v == n - 1) return w == 4 ? 0 : 1e9;
	if(~dp[v][w]) return dp[v][w];
	int ret = 1e9;
	if(str[v + 1] == w + 'a'){
		for(int i=0; i<10; i++){
			ret = min(ret, f(v + 1, i) + 2);
		}
		return dp[v][w] = ret;
	}
	for(int i=0; i<10; i++){
		ret = min(ret, g(v + 1, w, i) + 2);
	}
	if(!chk[v + 1]) ret = min(ret, f(v + 1, w));
	return dp[v][w] = ret;
}

int main(){
	scanf("%d %s",&n,buf);
	n = 0;
	int ecnt = 0;
	for(int i=0; buf[i]; i++){
		if(buf[i] == 'e'){
			ecnt++;
			chk[n] = 1;
		}
		else str[n++] = buf[i];
	}
	memset(dp, -1, sizeof(dp));
	memset(d2, -1, sizeof(d2));
	int ret = 1e9;
	for(int i=0; i<10; i++){
		ret = min(ret, f(0, i));
	}
	cout << ret + ecnt * 2 << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

vim.cpp: In function 'int main()':
vim.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %s",&n,buf);
  ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...