$Poj1037 A Decorative Fence$ 计数类$DP$

Poj  AcWing

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("
");
}
int main()
{
    int T;scanf("%d",&T);
    init();
    while(T--){scanf("%d%lld",&n,&c);solve();}
    return 0;
}