Description
Sol
这题很数位$DP$啊, 预处理$+$试填法
$F[i][j][k]$表示用$i$块长度不同的木板,当前木板(第$i$块)在这$i$块木板中从小到大排在第$j$位,构成栅栏的方案数.$k=0$表示处于低位,$k=1$表示处于高位.
$F[i][j][0]=\sum_{p=j}^{i-1}$
$F[i][j][1]=\sum_{p=1}^{j-1}$
然后这里有一个地方想了挺久的最终在$gql$的$blog$里找到了答案(怎样才能和$gql$一样神仙啊???),就是为什么$F[i][j][0]$的转移方程里$p$从$j$开始而不是$j+1$.这要看它的相对性$qwq$,因为现在第$i$块木板排第$j$,但是前$i-1$块木板里没有当前排第$j$的木板,也就是当前$(j+1,i)$的木板在$i-1$的情况下都会跌一名 : ))
预处理完之后就是"试填法"了!
外层枚举长度(种数)$i$,内层枚举第$i$块木板的长度.要记录第$i$块木板在前$i$块木板里的排名,然后累计当前选择下的栅栏总数,判断当前选择是否正确不是就继续循环下一个.....具体看代码叭.(代码是以前写的,变量名和上面所写的不太一样$OvO$)
Code
#include<iostream> #include<cstdio> #include<cstring> #define Rg register #define il inline #define db double #define ll long long #define mem(a,b) memset(a,b,sizeof(a)); #define go(i,a,b) for(Rg int i=a;i<=b;i++) #define yes(i,a,b) for(Rg int i=a;i>=b;i--) using namespace std; const int N=21; int n,ans[N]; ll c,a[N][N][2]; bool fl[N]; il void init() { a[1][1][0]=a[1][1][1]=1; go(len,2,20) go(i,1,len) { go(j,i,len-1)a[len][i][0]+=a[len-1][j][1]; go(j,1,i-1)a[len][i][1]+=a[len-1][j][0]; } } il void solve() { mem(fl,0);ll cnt=0; go(len,1,n) { int nm=0; go(i,1,n) { ll lc=cnt; if(fl[i])continue; nm++; if(len==1)cnt+=a[n][nm][0]+a[n][nm][1]; else { if(i>ans[len-1]&&(ans[len-1]<ans[len-2]||len<=2))cnt+=a[n-len+1][nm][1]; if(i<ans[len-1]&&(ans[len-1]>ans[len-2]||len<=2))cnt+=a[n-len+1][nm][0]; } if(cnt<c)continue; fl[i]=1;ans[len]=i;cnt=lc;break; } } go(i,1,n)printf("%d ",ans[i]);printf("\n"); } int main() { int T;scanf("%d",&T); init(); while(T--){scanf("%d%lld",&n,&c);solve();} return 0; }View Code