SCOJ 3843 ZUMA[기억 화 검색,dp]
1642 단어 dp
분석:기억 화 검색,,,,언어 조직 력 이 너무 나 빠 서 잘 모 르 겠 어 요...멘 붕 o(╯□╰)o
#include<stdio.h>
#include<string.h>
const int MAXN = 100+5;
const int K = 5+1;
int n,k;
int a[MAXN];
int dp[MAXN][MAXN][K];//dp[l][r][cnt];// l r, l cnt l
inline int min(int a,int b)
{
return a<b?a:b;
}
int solve(int left,int right,int cnt)// left cnt a[left] ， right
{
int &cur = dp[left][right][cnt];// cur
if(cur!=-1)return cur;
if(left==right)
{
cur = k-cnt-1;
return cur;
}
if(left>right)
{
cur = 0;
return cur;
}
if(cnt<k-1)
cur = solve(left,right,cnt+1)+1;
else
if(cnt>=k-1)// k-1 a[left] ，
cur = solve(left+1,right,0);
int i;
for(i=left+1;i<=right;i++)
{
if(a[i]!=a[left])continue;
int value = solve(left+1,i-1,0)+solve(i,right,min(cnt+1,k-1));// left,i
if(value<cur)cur = value;
}
return cur;
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(dp,-1,sizeof(dp));
int i;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("%d
",solve(0,n-1,0));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
