구간 dp poj3280 Cheapest Palindrome
제목: 일부 문자를 추가하거나 삭제하여 원열을 회문열로 바꾸기
dp[i][j]를 설정하면 [i, j] 구간을 회문열로 바꾸는 데 필요한 최소 대가를 표시합니다
i>j 또는 i==j일 때 dp[i][j]는 0과 같다고 생각한다
그럼 dp[i][j]가 어디로 옮겨올까요?
먼저, S[i]=S[j]일 때 [i, j]를 메신저열로 바꾸고 싶다면 [i+1, j-1]도 메신저열일 수밖에 없기 때문에 dp[i][j]=dp[i+1, j-1]
하면, 만약, 만약...S[j]시 추가 또는 삭제 필요
S[i]의 왼쪽에 S[j]를 추가하면 dp[i][j]=dp[i][j-1]+S[j]의 비용이 증가합니다
S[j]를 삭제하면 dp[i][j]=dp[i][j-1]+S[j]를 삭제하는 비용
S[j]의 오른쪽에 S[i]를 추가하면 dp[i][j]=dp[i+1][j]+S[i]의 비용이 증가합니다
S[i]를 삭제하면 dp[i][j]=dp[i+1][j]+S[i]를 삭제하는 비용
그럼 왜 S[j]의 왼쪽에 S[i]를 추가하지 않았을까요?
만약 그렇다면 S[j]는 무시되고 [l,r]는 메모가 아니다.
그리고 구간 dp는 일반적으로 보폭에 따라 매거하는 것이기 때문에 비교적 간단한 처리 방법은 바로 기억화 검색으로 편리하고 틀리기 쉽다
그러나 단점은 비교적 느리고 창고가 터지기 쉬우므로 때때로 자신이 없으면 창고 확장 코드를 넣는 것이 가장 좋다는 것이다
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
#include<functional>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MX = 2e3 + 5;
const int INF = 0x3f3f3f3f;
#pragma comment(linker,"/STACK:102400000,102400000")
char S[MX];
int cost[26];
int dp[MX][MX];
int DP(int L, int R) {
if(L > R) return 0;
if(dp[L][R]) return dp[L][R];
if(S[L] == S[R]) {
return dp[L][R] = DP(L + 1, R - 1);
}
int ret = dp[L][R] = min(DP(L, R - 1) + cost[S[R] - 'a'], DP(L + 1, R) + cost[S[L] - 'a']);
return ret;
}
int main() {
int n, L;
//freopen("input.txt", "r", stdin);
while(~scanf("%d%d", &n, &L)) {
memset(dp, 0, sizeof(dp));
scanf("%s", S + 1);
for(int i = 1; i <= n; i++) {
char s[5];
int u, v;
scanf("%s%d%d", s, &u, &v);
cost[s[0] - 'a'] = min(u, v);
}
printf("%d
", DP(1, L));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
