[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