51nod 1779逆序对统计(状压DP)

时间:2022-08-16 04:57:37

按照插入数的大小排序,

然后依次进行dp。

用一个状态表示n个数是否被选了

10110 就是表示第1、3、4个位置都选了

那么如果此时这个数该填到5这个位置,那么必定会造成一个逆序(因为下一个数会填到2,下一个数必定比这个数大)

也就是转移的时候看插入位置前有多少个0,进行转移

写的时候有一些小技巧

(直接用记忆化统计0的个数超时了,这里有一个递推的技巧)

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[][(<<)+], f[(<<)+];
int n, m, a[]; int main()
{
cin>>n>>m;
for(int i = ; i <= m; i++) cin>>a[i];
for(int i = ; i < n; i++) f[<<i] = ;
for(int i = ; i < (<<n); i++) f[i] = f[i&-i]+f[i^(i&-i)];
memset(dp[], , sizeof(dp[]));
dp[][] = ;
int all = (<<n)-;
for(int i = ; i <= m; i++){
for(int s = ; s <= all; s++){
if(dp[(i-)&][s] < ) continue;
dp[i&][s] = max(dp[i&][s], dp[(i-)&][s]);
if((s&(<<(n-a[i]))) == ){
dp[i&][s|(<<(n-a[i]))] = max(dp[i&][s|(<<(n-a[i]))], dp[(i-)&][s] + (a[i]--f[s>>(n-a[i]+)]));
}
}
memset(dp[(i-)&], , sizeof(dp[(i-)&]));
}
cout<<dp[m&][(<<n)-]<<endl;
return ;
}