首页 > 其他分享 >[PA2019] Desant Solution

[PA2019] Desant Solution

时间:2024-12-28 19:20:55浏览次数:7  
标签:cnt PA2019 int Solution first t1 now Desant fo

[PA2019] Desant Solution

原题链接

题目大意:给定一个长为 \(n(n\le 40)\) 的排列,对于每个 \(i\) 求出长度为 \(i\) 的子序列逆序对最少有多少,并且求出有多少个长度为 \(i\) 的子序列逆序对最少。

解题思路:首先有一个暴力的做法,设 \(f_{i,S}\) 表示考虑完前 \(i\) 个数,选择了集合 \(S\) 的最少逆序对数、方案数。这样做至少是 \(O(n2^n)\),非常不优美。我们发现我们只关心比当前位置大的数有多少个,所以我们把 \(S\) 中所有数都记录下来是有些多余的。考虑优化状态。

对于考虑完了前 \(i\) 个数,我们把 \(i\) 以后的数排序,记为 \(x_1,x_2,\cdots\),我们只需要记录 \([1,x_1),(x_2,x_3),\cdots,(x_{end},n]\) 这样每个区间内选了多少个数即可。于是我们可以设状态 \(f_{i,T_1,T_2,\cdots}\),\(T_i\) 表示第 \(i\) 个区间内选了多少个数。

考虑计算状态的个数,我们就是求和为 \(n\) 的若干个数乘积最大是多少。严谨证明我不会,但是根据小学奥数,我们只要尽可能多拆 \(3\),其次拆 \(2\),尽量少拆成 \(1\),这是因为如果我们考虑一个大于 \(3\) 的数,把它对半拆开乘积一定会更大,如 \(5<2\times 3\)。因此可以想到,最坏情况下,状态数是 \(O(3^{\frac n 3})\),实际上这与严谨证明下的结论一致。因此状态数是可行的。

再回到状态上来,我们可以对于第 \(i\) 个长度为 \(len_i\) 的区间,用第 \(i\) 位上的 \((len_i+1)\) 进制表示,即记 \(w_i=\prod_{j=1}^{i-1}(len_j+1)\),设 \(cnt_i\) 为第 \(i\) 个区间选了多少个数,则 \(T=\sum_{i=1}^{end}cnt_iw_i\),这样就能用整型表示状态 \(f_{i,T}\),用 vector 连续开 \(\prod (len_i+1)\) 个位置即可,比哈希快多了。

而对于转移,每次决策选或不选都会合并两个区间。暴力地拆出状态的每一位和合并状态的每一位即可。

时间复杂度 \(O(n^2n^\frac{n}3)\),注意方案数要开 long long

AC 代码:

int n;
const int N=45;
int a[N];
int l[N],w[N][N],c[N][N];
vector<pair<int,ll> > f[N];
int now[N];
void getmax(pair<int,ll> &x,pair<int,ll> y){
	if(x.first>y.first)x=y;
	else if(x.first==y.first)x.second+=y.second;
}
signed main(){
	read(n);
	fo(i,1,n){
		read(a[i]);
	}
	fo(i,0,n){
		fo(j,i+1,n){
			c[i][++l[i]]=a[j];
		}
		c[i][++l[i]]=n+1;
		sort(c[i]+1,c[i]+1+l[i]);
		int t=1;
		fo(j,1,l[i]){
			w[i][j]=t;
			t*=c[i][j]-c[i][j-1];
		}
		f[i]=vector<pair<int,ll>>(t,{1e9,0});
	}
	f[0][0]={0,1};
	fo(i,0,n-1){
		int at=0;
		fo(j,1,l[i])if(c[i][j]==a[i+1])at=j;
		fu(j,0,f[i].size()){
			int t=j;
			fd(k,l[i],1){
				now[k]=t/w[i][k];
				t%=w[i][k];
			}
			int cnt=0;
			fo(k,at+1,l[i])cnt+=now[k];
			int t1=0,t2=0;
			fo(k,1,at-1)t1+=now[k]*w[i+1][k];
			fo(k,at+2,l[i])t1+=now[k]*w[i+1][k-1];
			t2=t1;
			t1+=(now[at]+now[at+1])*w[i+1][at];
			t2+=(now[at]+now[at+1]+1)*w[i+1][at];
			getmax(f[i+1][t1],f[i][j]);
			getmax(f[i+1][t2],{f[i][j].first+cnt,f[i][j].second});			
		}
	}
	fo(i,1,n)write(f[n][i].first,' ',f[n][i].second,'\n');
	return 0;
}

标签:cnt,PA2019,int,Solution,first,t1,now,Desant,fo
From: https://www.cnblogs.com/dccy/p/18637829

相关文章