Garland
참조: Codeforces Round #612(Div.2) A~E2 문제 해결
폭력적인 방법을 시도해 보았지만 그다지 좋지 않아서 dp로 전전하였다
모두 네 개의 상태\(dp[x][i][j][bj]\)가 있는데 i개의 홀수가 있음을 나타낸다. j개의 짝수는 사용할 수 있고 x~n 위치의 복잡도 합의 최소값이며 위치 x-1의 상태는 bj(1은 홀수, 0은 짝수)이다.
dfs로 기억화 검색을 하여 최상의 결과를 얻다.
코드:
// Created by CAD on 2020/1/7.
#include
#define inf 0x3f3f3f3f
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;
int p[105];
const int maxn=105;
int dp[maxn][maxn][maxn][3];
int n;
int dfs(int x,int i,int j,int bj)
{
if(x==n+1) return 0;
if(~dp[x][i][j][bj]) return dp[x][i][j][bj];
dp[x][i][j][bj]=0;
if(p[x])
{
if((p[x]&1)==bj||bj==2)
return dp[x][i][j][bj]=dfs(x+1,i,j,p[x]&1);
else return dp[x][i][j][bj]=dfs(x+1,i,j,p[x]&1)+1;
}
else
{
int a=inf,b=inf;
if(bj==2)
{
if(i>0) a=dfs(x+1,i-1,j,1);
if(j>0) b=dfs(x+1,i,j-1,0);
}
else if(bj==1)
{
if(i>0) a=dfs(x+1,i-1,j,1);
if(j>0) b=dfs(x+1,i,j-1,0)+1;
}
else
{
if(i>0) a=dfs(x+1,i-1,j,1)+1;
if(j>0) b=dfs(x+1,i,j-1,0);
}
return dp[x][i][j][bj]+=min(a,b);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int odd=n/2+n%2,even=n/2;
for(int i=1;i<=n;++i)
{
cin>>p[i];
if(p[i])
{
if(p[i]&1) odd--;
else even--;
}
}
mst(dp,-1);
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.