글 읽기 - 반례 부탁드립니다.

nemo 4년 전 0

dp[i][j][k] = i부터 j까지를 k라는 색깔로 채우는데 걸리는 최소횟수라 정의하고
dp[i][j]는 dp[i][j-1],dp[i+1][j]를 재귀호출하고 채우게끔 구현했는데
왜 틀렸는지 잘 모르겠습니다

#include<bits/stdc++.h>
#define ll long long
#define INF 2e9
using namespace std;
int N,K,arr[201],dp[201][201][21];
int f(int a, int b, int k){
	if(dp[a][b][k]!=INF) return dp[a][b][k];
	int ret=INF;
	for(int i=1;i<=20;i++){
		int l=dp[a][b-1][i], r=dp[a+1][b][i];
		if(l==INF)
			l=f(a,b-1,i);
		if(r==INF)
			r=f(a+1,b,i);
		if(arr[b]!=i) l++; 
		if(arr[a]!=i) r++;
		if(i==k) ret=min(ret,min(l,r));
		else ret=min(ret,min(l,r)+1);
	}
	dp[a][b][k]=ret;
	return ret;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    for(int i=0;i<=200;i++)
		for(int j=0;j<=200;j++)
			for(int k=0;k<=20;k++)
				dp[i][j][k]=INF;
    cin>>N>>K; 
    for(int i=1;i<=N;i++){
    	cin>>arr[i];
		dp[i][i][arr[i]]=0;
		for(int j=1;j<=20;j++){
			if(j==arr[i]) continue;
			dp[i][i][j]=1;
		}
	}
	int ans=INF;
	for(int i=1;i<=20;i++)
		ans=min(ans,f(1,N,i));
    cout<<ans;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드립니다.

nemo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말