按照插入数的大小排序,
然后依次进行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 ;
}