如何做网站分析,wordpress插件破解下载地址,做信息类网站,昆明本地网站传送门
题意#xff1a;给一个长为NNN的序列aaa#xff0c;每次操作交换两个相邻位置#xff0c;求最少操作次数使得所有相同的值连成一片。 N≤400000N \leq 400000N≤400000,ai≤20a_i \leq20ai≤20
我们发现aia_iai很小#xff0c;盲猜单独考虑
我们重新确认一个…传送门
题意给一个长为NNN的序列aaa每次操作交换两个相邻位置求最少操作次数使得所有相同的值连成一片。
N≤400000N \leq 400000N≤400000,ai≤20a_i \leq20ai≤20
我们发现aia_iai很小盲猜单独考虑
我们重新确认一个宏大的时空观
把所有位置按值分组然后一组一组加进去。在某一组没有加之前这个位置是不存在的即1 3 2在没有加3时1 2是相邻的。
设cnt[i][j]cnt[i][j]cnt[i][j]表示只有iii和jjj两组数时把所有iii移到jjj的前面的最小操作次数
这个可以暴力枚举iii和jjj然后双指针即可
考虑状压
设dp[S]dp[S]dp[S]表示当前加入的数的状态为SSS的最小操作次数 我们新加一个数时把散装的都移到最前面。因为cntcntcnt是单独考虑的所以加起来就可以了
即
dp[S]mini∈S{dp[S−{i}]∑j∈S,i≠jcnt[i][j]}dp[S]\min_{i \in S}\{dp[S-\{i\}]\sum_{j\in S,i\neq j}cnt[i][j]\}dp[S]i∈Smin{dp[S−{i}]j∈S,ij∑cnt[i][j]}
最后的dp[2n−1]dp[2^n-1]dp[2n−1]即答案
复杂度O(na22aa2)O(na^22^aa^2)O(na22aa2)
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
using namespace std;
typedef long long ll;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
vectorint v[20];
ll cnt[20][20],dp[120];
int main()
{int nread();for (int i1;in;i) v[read()-1].push_back(i);for (int i0;i20;i)for (int j0;j20;j)if (i!j){int pos-1;for (int k0;kv[i].size();k){while (pos1v[j].size()v[j][pos1]v[i][k]) pos;cnt[i][j]pos1;}}dp[0]0;for (int s1;s(120);s){dp[s]1e18;for (int i0;i20;i)if (s(1i)){ll sum0;for (int j0;j20;j)if (s(1j))sumcnt[i][j];dp[s]min(dp[s],dp[s^(1i)]sum); } }coutdp[(120)-1];return 0;
}
