[USACO Section 3.2] 01串 Stringsobits (动态规划)

题目链接

Solution

贼有意思的 DP, 也可以用组合数学做.

\(f[i][j]\) 代表前 \(i\) 位,有 \(j\) 个 \(1\) 的方案数.

转移方程很简单 : \(f[i][j]=f[i-1][j]+f[i-1][j-1]\)

然后可以按位判断答案上是否为 \(1\) .

如何判断?

如果当前 \(f[i][L]\) 小于 \(I\) ,那么我们所要的方案一定 \(i\) 位上为 \(1\);

同时用 \(I\) 减去 \(f[i][L]\) , \(L\) 同时减掉 \(1\);

Code

#include<bits/stdc++.h>

using namespace std;

int f[52][52]={0},ans[52];

int N, L;

long long I; 

int main()

{

    cin>>N>>L>>I;

    for (int i=0;i<=N;i++)f[i][0] =f[0][i]=1;

    for (int i=1;i<=N;i++)

        for (int j=1;j<=N;j++)

            if(j<=i)

            f[i][j]=f[i-1][j-1] + f[i-1][j];

            else f[i][j]=f[i][i];

    for (int i=N;i >=1;i--)

    {

        if (I>f[i-1][L])

        {

            cout<<1;

            I-=f[i-1][L];

            L--;

        }

        else cout<<0 ;

    }

}

巴特西

[USACO Section 3.2] 01串 Stringsobits (动态规划)

题目链接

Solution

Code

最新文章

热门文章