1779 逆序对统计基准时间限制:1 秒 空间限制:131072 KB 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
这个其实就是用树状数组求逆序对啊,搞进位运算就行了
#include <bits/stdc++.h>
using namespace std;
const int N = , M = (<<) + ;
int n, m, a[N], all, ff[M], f[][M], cur;
int main() {
scanf("%d%d",&n,&m);
for(int i=; i<=m; i++){
int p;
scanf("%d",&p);
a[i]=p-;
}
all = <<n;
for(int i=; i<=n; i++) ff[<<i] = ;
for(int i=; i<all; i++) ff[i] = ff[i&-i] + ff[i^(i&-i)];
memset(f, -, sizeof(f));
f[cur][] = ;
for(int i=; i<m; i++, cur ^= ) {
int *g = f[cur], *d = f[cur^];
for(int s=; s<all; s++) if(g[s] != -) {
d[s] = max(d[s], g[s]);
if(~ s & (<<a[i+])) {
int ns = s | (<<a[i+]);
d[ns] = max(d[ns], g[s] + ff[ns >> (a[i+] + )]);
}
g[s] = -;
}
}
printf("%d\n", f[cur][all-]);
return ;
}
这个状压dp很奇妙,点进去看真相