2018 ACM-ICPC 徐州邀请赛 B.Array 滚动dp+前缀和+离线处理

63 阅读 0 评论 42 点赞

我是靠谱客的博主合适白昼，最近开发中收集的这篇文章主要介绍2018 ACM-ICPC 徐州邀请赛 B.Array 滚动dp+前缀和+离线处理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：

Array

题意：

多组样例，每组给一个1->n的数组，问全排列方案中，有多少种方案会使得满足i＜j且ai>aj的实数对(i,j)的个数%1e9+7后为k

数据规模：

0<样例数,n,k<=5000
内存限制：65536K
时间限制：1000ms
思路：

大佬说，遇事不决先打表，首先暴力打个表，ans数组存方案数，下标为k。

#include <bits/stdc++.h>
using namespace std;
int ans[500];
int main(){
	for(int n = 1;n <= 10;n++){
		memset(ans,0,sizeof(ans));
		int num[n];
		int maxm = 0;
		for(int i = 0;i < n;i++)num[i] = i+1;
		do{
			int sum = 0;
			for(int i = 0;i < n;i++)
			for(int j = i+1;j < n;j++)
			if(num[i] > num[j])sum++;
			ans[sum]++;
			maxm = max(maxm,sum);
		}while(next_permutation(num,num+n));
		for(int i = 0;i <= maxm;i++)
		cout << ans[i] << " ";
		cout << endl;
	}
	
	return 0;
}

打表结果：

每个n一行，每列代表一个k(从0开始数)

选第八行丢到oeis里，分析说是Weyl group的第八行。。随后wiki查了半天没搞懂这个group

目测找规律，从前几列看出大概满足a[i][j] = a[i-1][j] + a[i][j-1],可是第五行的22不满足这个规律。

如果n时每个k的方案数已知(知道某一行)，(n+1)时(下一行)逆序方案数可以看作n的全排列中添加(n+1)这个数，位置不定，所以找到能产生k对逆序数的排列：

将n插入到1,2,3……n-1中，如果插入到最左端，将产生新的n-1对逆序对，如果插入到n-1之后，将产生0对新的逆序对，所以当序列长度为n时，想要k对逆序对的排列方案数，只需在n-1时找到逆序对介于[k-n+1,k]的排列数即可。
即：a[i][j] = a[i-1][j-i+1] + a[i-1][j-i+2] + … + a[i-1][j]

如果j-i+1<0,从0开始处理。由于涉及到求数组区间和，故采用前缀和数组保存。

5000x5000的int所需内存约为95.36MB，大于限制内存，故动态规划需要采用滚动数组形式，由于每一行只由它的上一行得来，故滚动数组开两行即可。

由于多组样例，n可能不按顺序，为避免多次从头开始dp，采用离线处理，读取完全部询问之后根据n排序，n从小到大，从1到5000跑一遍，得出全部询问的结果后按序号顺序输出。

代码：

#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9+7;
int num[2][5010];
int ans[5010];
struct node{
	int id,n,k;
}p[5010];
bool cmp(const node &a,const node &b){
	if(a.n == b.n)return a.k < b.k;
	return a.n < b.n;
}
int main(){
	int t = 0;
	while(~scanf("%d %d",&p[t].n,&p[t].k)){
		p[t].id = t;
		t++;
	}
	sort(p,p+t,cmp);
	int now = 0;
	num[1][0] = num[1][1] = 1;
	while(1 == p[now].n){
		if(p[now].k == 0)ans[p[now].id] = 1;
		else ans[p[now].id] = 0;
		now++;
	}
	for(int i = 2;i <= 5000;i++){
		memset(num[i&1],0,sizeof(num[i&1]));
		num[i&1][0] = 1;
		int sum = (i-1)*i/2;
		for(int j = 1;j <= 5005 && j <= sum;j++){
			if(j+1 <= i)num[i&1][j] = num[(i-1)&1][j];
			else num[i&1][j] = num[(i-1)&1][j] - num[(i-1)&1][j-i];
			if(num[i&1][j] < 0)num[i&1][j] += mod;
			else if(num[i&1][j] >= mod)num[i&1][j] %= mod;
		}
		while(i == p[now].n){
			ans[p[now].id] = num[i&1][p[now].k];
			now++;
		}
		for(int j = 1;j <= 5005;j++){
			num[i&1][j] += num[i&1][j-1];
			if(num[i&1][j] >= mod)num[i&1][j] %= mod;
		}
	}
	for(int i = 0;i < t;i++)
	printf("%dn",ans[i]);
	return 0;
}