CodeForces 1238 - E 키보드 구 매 (상 압 DP)

15001 단어 CF 200 문제 계획DP
제목:
전송 문
생각:
먼저 모든 문자 에 대한 공헌 을 미리 처리 합 니 다. 예 를 들 어 abcd 는 (a, b), (b, c), (c, d) 모두 하나 입 니 다. 새 디스크 에 있 는 문자 위치 pos 가 있 으 면 그 와 관련 된 공헌 쌍 에서 번호 가 큰 쌍 에서 그것 을 빼 야 합 니 다. 즉 - pos, 반대로 그것 을 더 하면 + pos 입 니 다.이 를 통 해 알 수 있 듯 이 우 리 는 하나의 문자 의 공헌 을 단독으로 계산 할 수 있 기 때문에 우 리 는 직접 매 거 진 순 서 를 고려 하여 매번 최소 치 를 유지 하 는 것 을 고려 할 수 있 습 니 다. 그러나 상 압 dp 가 이동 하 는 과정 에서 마침 순 서 를 일일이 매 거 할 수 있 습 니 다.
Ac_Code: 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define fir first
#define sec second
using namespace std;
 
const int maxn = (1<<20)+7;
const int INF = 1e9+7;
 
int n,m;
string s;
long long dp[maxn];
long long val[maxn][25];
int vis[maxn];
int len[maxn];
int bit[25];
int mn[30][30];
int all[30];
 
int main() {
    cin>>n>>m>>s;
    bit[0] = 1;
    for(int i=1;i<=m;i++) bit[i] = bit[i-1]*2;
    for(int i=1;i<n;i++) {
        int d = s[i]-'a';
        int dd = s[i-1]-'a';
        if(d == dd) continue;
        mn[dd][d]++;
        mn[d][dd]++;
        all[d]++;
        all[dd]++;
    }
    int up = (1<<m);
    for(int i=0;i<up;i++) dp[i] = INF,dp[0] = 0;
    for(int i=0;i<up;i++) {
        for(int j=0;j<m;j++) {
            if(bit[j]&i) continue;
            int res = (i|bit[j]);
            dp[res] = min(dp[res],dp[i] + (2*val[i][j]-all[j])*(len[i]+1));
            if(vis[res] == 0) {
                for(int l=0;l<m;l++) {
                    val[res][l] = val[i][l] + mn[j][l];
                }
                len[res] = len[i]+1;
            }
            vis[res] = 1;
        }
    }
    printf("%lld
", dp[up-1]);
    return 0;
}
CF contest/382/B. Number Busters
AndroidWidget 실천 - Everyday Tips 개발(2)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage