제출 #1157130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157130		alexander707070	Giraffes (JOI22_giraffes)	C++20	59 / 100	45 ms	55628 KiB

giraffes

#include<bits/stdc++.h>
#define MAXN 307
using namespace std;

int n,a[MAXN];
int dp[MAXN][MAXN][MAXN];

int main(){

	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}

	for(int len=1;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			int used=n-len;

			for(int pref=0;pref<=used;pref++){
				if(len==1){
					dp[l][r][pref]=(a[l]==pref+1);
				}else{
					dp[l][r][pref]=max( max(dp[l+1][r][pref+1] , dp[l][r-1][pref+1]) , max(dp[l+1][r][pref] , dp[l][r-1][pref]) );

					if(pref+1==a[l])dp[l][r][pref]=max(dp[l][r][pref],dp[l+1][r][pref+1]+1);
					if(pref+1==a[r])dp[l][r][pref]=max(dp[l][r][pref],dp[l][r-1][pref+1]+1);

					if(n-(used-pref)==a[l])dp[l][r][pref]=max(dp[l][r][pref],dp[l+1][r][pref]+1);
					if(n-(used-pref)==a[r])dp[l][r][pref]=max(dp[l][r][pref],dp[l][r-1][pref]+1);
				}
			}
		}
	}

	cout<<n-dp[1][n][0]<<"\n";

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 41