51nod1779 逆序对统计

1779 逆序对统计  基准时间限制：1 秒 空间限制：131072 KB 分值: 80  难度：5级算法题  收藏  关注 lyk最近计划按顺序做n道题目，每道题目都分为很多分数档次，lyk觉得这些题太简单了，于是它想到了一个好玩的游戏。 lyk决定将每道题目做出其中的某个分数，使得这n道题目的逆序对个数最多。 为了方便，假设共有m个分数档次，并且会给m个分数档次分配一个题目编号，表示该题目会出现这个分数档次。 题目保证每道题都存在至少一个分数档次。（例如样例中5道题目的分数分别是5,6,3,4,7,共有4个逆序对） Input 第一行两个数n,m(n<=20,m<=100)。 接下来m行，每行一个数ai，表示第ai道题目可能会有i这个分数的档次。 Output 一个数表示最多逆序对个数。 Input示例 5 7 1 2 3 4 1 2 5 Output示例 4

题解：

点击打开链接

按照插入数的大小排序，

然后依次进行dp。

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

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

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

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

代码：

#include<bits/stdc++.h> using namespace std; int n,m,i,x,ii,j,sum,f[2000001]; int main(){ scanf("%d%d",&n,&m); for(i=1;i<(1<<n);i++)f[i]=-500000000; for(ii=1;ii<=m;ii++){ scanf("%d",&x);x--; for(i=0;i<(1<<n);i++){ if(!(i>>x&1)&&f[i]!=-500000000){ sum=0; for(j=x+1;j<=n;j++)sum+=i>>j&1; f[i|(1<<x)]=max(f[i|(1<<x)],f[i]+sum); } } } printf("%d",f[(1<<n)-1]); }