UVALive 4857 Halloween Costumes
1495 단어 live
1、이 지점에서 입는 옷은 해당 지점에서 쓸 옷만 있으면 벗는다.그래서 dp[l]r]=min(dp[l+1]r]+1, dp[l]r]).
2. 옷은 그대로 둔다.이 단계는 뒤에 이 옷을 써야만 보존을 선택할 수 있다는 것을 명확히 해야 한다.만약 현재 위치가 i라면 j 위치와 현재 위치의 옷이 같다.현재의 옷을 고려하여 j 위치까지 입을 수 있다.이 기간에도 이 옷이 사용될 수 있기 때문이다.그래서 우리는 j 위치를 보류했다. 이렇게 하면 전체 구간 l, r가 이 옷을 사용할 수 있다.그래서 dp[l][r]=min(dp[l]r], dp[l+1]j]+dp[j+1]r);
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 110;
const int INF = 1e9 + 7;
int dp[N][N];
int n, m, c[N];
int dfs(int l, int r)
{
if(l > r) return 0;
if(l == r) return 1;
if(dp[l][r] >= 0) return dp[l][r];
int &ret = dp[l][r];
ret = dfs(l + 1, r) + 1;
for(int i = l + 1; i <= r; i ++)
{
if(c[i] == c[l])
{
ret = min(ret, dfs(l + 1, i) + dfs(i + 1, r));
}
}
return ret;
}
int main()
{
int t, cas = 1;
scanf("%d", &t);
while(t --)
{
scanf("%d%d", &n, &m);
c[0] = -1;
for(int i = 1; i <= n; i ++)
{
scanf("%d", &c[i]);
if(c[i] == c[i - 1])
n --, i --;
}
CLR(dp, -1);
printf("Case %d: %d
", cas ++, dfs(1, n));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vvalive 6323 상태 압축 DP텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
