Codeforces 1215E 状压DP
2024-10-07 12:07:53
题意:给你一个序列,你可以交换序列中的相邻的两个元素,问最少需要交换多少次可以让这个序列变成若干个极大的颜色相同的子段。
思路:由于题目中的颜色种类很少,考虑状压DP。设dp[mask]为把mask为1的颜色从后往前放置的最小花费。那么我们新添加一种颜色时需要知道要转移多少次,所以我们需要预处理转移矩阵c[i][j]。c[i][j]的意思是只考虑i, j两种元素,把所有的元素i移动到元素j前面的最小花费,预处理好之后暴力转移即可。
代码:
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 400010;
vector<int> 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<int> 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\n", f[(1 << 20) - 1]);
}
最新文章
- iOS多线程之9.自定义NSOperation
- Asp.net 设置GridView自适应列宽不变形
- Excel单元格发生变化后,使用Outlook给特定的人发邮件
- juery 实现下拉框多选 jquery-multiselect
- rpmdb出问题,重建rpmdb库
- 基于Visual C++2012拆解世界五百强面试题--题3
- bzoj 1046 : [HAOI2007]上升序列 dp
- 高频dom操作和页面性能优化(转载)
- Reflection and array
- SqlServer误删数据恢复
- C/JS_实现冒泡排序
- SQL Server清空日志以及查看日志大小语句
- Sql Server查询性能优化之不可小觑的书签查找
- echart知识点、常用图形
- web10 动态action的应用
- Python 类编码风格
- docker-4-镜像
- postgresql一般crud存储过程参考[转]
- ios 更改UITableview中Section的字体颜色
- 【洛谷P3909】异或之积