Codeforces 1215 E 상 압 DP
사고방식: 제목 의 색깔 종류 가 매우 적기 때문에 상 압 DP 를 고려한다.dp [mask] 를 설정 하여 mask 를 1 로 하 는 색 을 뒤에서 앞으로 배치 하 는 데 최소 비용 을 들 입 니 다.그러면 우리 가 새로운 색 을 추가 할 때 몇 번 을 옮 겨 야 하 는 지 알 아야 하기 때문에 우 리 는 행렬 c [i] [j] 를 미리 처리 해 야 합 니 다.c [i] [j] 는 i, j 두 가지 요소 만 고려 하여 모든 요소 i 를 요소 j 앞 에 이동 시 키 는 최소 비용 으로 미리 처리 한 후에 폭력 으로 이동 하면 된다 는 뜻 이다.
코드:
#include
#define LL long long
using namespace std;
const int maxn = 400010;
vector b[20];
int a[maxn];
LL f[1 << 20];
LL c[20][20];
int main() {
int n;
scanf("%d", &n);
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[a[i] - 1].push_back(i);
}
for (int i = 0; i < 20; i++) {
if(!b[i].size()) continue;
for (int j = 0; j < 20; j++) {
if(!b[j].size() || i == j) continue;
int p = 0;
for (int k = 0; k < b[i].size(); k++) {
while(p < b[j].size() && b[j][p] < b[i][k]) p++;
// if(p < b[j].size())
c[i][j] += p;
}
}
}
f[0] = 0;
for (int i = 0; i < (1 << 20); i++) {
vector d;
d.clear();
for (int j = 0; j < 20; j++) {
if((i >> j) & 1) {
d.push_back(j);
}
}
for (int j = 0; j < 20; j++) {
if(((i >> j) & 1) == 0) {
LL sum = 0;
for (int k = 0; k < d.size(); k++) {
sum += c[d[k]][j];
}
f[i ^ (1 << j)] = min(f[i ^ (1 << j)], f[i] + sum);
}
}
}
printf("%lld
", f[(1 << 20) - 1]);
}
다음으로 전송:https://www.cnblogs.com/pkgunboat/p/11533983.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
