POJ 3280 Cheapest Palindrome 구간 dp

3420 단어 동적 기획
제목: 모든 문자를 추가하거나 삭제하는 데 일정한 대가를 치러야 하는 문자열을 드리겠습니다. 이 문자열을 메모로 바꾸는 최소한의 대가가 무엇인지 물어보십시오.
우선 구조수 그룹 dp[i][j]는 i에서 j까지는 메신저가 소비하는 대가를 나타낸다. 한 문자를 추가하고 한 문자를 삭제하는 것은 메신저가 등가이기 때문에 양자 대가가 더 적은 것을 취하면 된다.len은 문자열의 길이입니다.그러면 dp의 범위는 1층 i가len-1에서 0까지이고 2층은 i+1에서len-1까지이다.이렇게 하면 dp[i][j]를 회문열로 구성할 때.dp[i+1][j]와 dp[i][j+1]만 얻을 수 있고, 양자가 회문열로 변하는 대가는 이미 알고 있다.따라서 점차적인 형식은str[i]==str[j]일 때:
dp[i][j]=dp[i+1][j−1] d p [ i ] [ j ] = d p [ i + 1 ] [ j − 1 ]
stri]!=str[j]시:
dp[i][j]=min(dp[i+1][j]+cost[i],dp[i][j−1]+cost[j]) d p [ i ] [ j ] = m i n ( d p [ i + 1 ] [ j ] + c o s t [ i ] , d p [ i ] [ j − 1 ] + c o s t [ j ] )
코드는 다음과 같습니다.
#include
#include
#include
#include
#include
#include

using namespace std;
const int MAX = 2010;
const int INF = 0x3f3f3f3f;
char str[MAX];
int cost[MAX],dp[MAX][MAX];
int N,M;
void solve(){
    memset(dp,0,sizeof(dp));
    for(int i=M-1;i>=0;--i){
        for(int j=i+1;j//         ,       INF
            if(str[i] == str[j])
                dp[i][j] = dp[i+1][j-1];
            else
                dp[i][j] = min(dp[i+1][j]+cost[str[i]],dp[i][j-1]+cost[str[j]]);
            //  dp[i+1][j],dp[i][j-1]            .
        }
    }
    cout << dp[0][M-1] << endl;
}
int main(void){
    cin >> N >> M;
    cin >> str;
    char ch;
    int add,del;
    for(int i=1;i<=N;++i){
        cin >> ch >> add >> del;
        cost[ch] = min(add,del);
    }
    solve();
    return 0;
}

좋은 웹페이지 즐겨찾기