codeforces 1132F 구간 DP

9053 단어 구간DP

codeforces 1132F


제목:


길이가 n인 문자열을 지정하면 모든 자모가 같은 문자열을 임의의 순서로 삭제할 수 있습니다.길이가 n인 문자열을 지정하면 모든 자모가 같은 문자열을 임의의 순서로 삭제할 수 있습니다.길이가 n인 문자열을 지정하면 모든 자모가 같은 문자열을 임의의 순서로 삭제할 수 있습니다.- 모든 문자의 최소 작업 수를 삭제합니다.- 모든 문자의 최소 작업 수를 삭제합니다.- 모든 문자의 최소 작업 수를 삭제합니다.

문제 풀이:


d p [l] [r]는 구간 [l, r] 내의 모든 문자를 삭제하는 것이 가장 좋은 것을 나타낸다.dp[l][r]는 구간 [l,r]의 모든 문자를 삭제하는 것이 가장 좋은 결과를 나타낸다.dp[l][r]는 구간 [l,r]의 모든 문자를 삭제하는 것이 가장 좋은 결과를 나타낸다.
  • s[l]=s[r]시, dp[l][r]=dp[l+1][r-4-1]+1s[l]=s[r]시, dp[l][r]=dp[l+1][r-1]+1s[l]=s[r]시, dp[l][r]=dp[l+1][r+1][r-1]+1
  • s [ l ] ≠ s [ r ] , d p [ l ] [ r ] = m i n ( d p [ l + 1 ] [ r ] , d p [ l ] [ r − 1 ] ) + 1 s[l]≠s[r],dp[l][r] = min(dp[l+1][r], dp[l][r-1])+1 s[l]̸​=s[r],dp[l][r]=min(dp[l+1][r],dp[l][r−1])+1
  • 매거분할점 k, dp[l][r] = m i n(dp[l] [r], dp[l] [k] + dp[k] [r] [r] -1) 매거분할점 k, dp[l] [r] = min(dp[l] [r], dp[l] [k] + dp[k] [k] [r] -1) 매거분할점 k, dp[l] [r] =(dpl] [r], [dpl] [45l] [dr670k] [810]
    #include 
    using namespace std;
    const int N = 501;
    char s[N];
    int dp[N][N];
    
    int main() {
        int n;
        cin >> n;
        for(int i = 1 ; i <= n ; i++){
            cin >> s[i];
        }
        for(int i = 1 ; i <= n ; i++){
            dp[i][i] = 1;
        }
        for(int len = 2 ; len <= n ; len++){
            for(int l = 1, r = len ; r <= n ; l++, r++){
                if(s[l] == s[r]){
                    dp[l][r] = dp[l+1][r-1]+1;
                }
                else{
                    dp[l][r] = min(dp[l+1][r], dp[l][r-1])+1;
                }
                for(int k = l ; k <= r ; k++){
                    dp[l][r] = min(dp[l][r], dp[l][k]+dp[k][r]-1);
                }
            }
        }
        cout << dp[1][n] << endl;
        return 0; 
    }
    
  • 좋은 웹페이지 즐겨찾기