[CF295C] Greg and Friends - dp

Description

有一只载重为 \(k \le 5\times10^3\) 的船在两岸之间往返，有 \(n \le 50\) 个人要过河，每个人的体重只能使 \(50\) 或 \(100\)，问最少的来回次数以及对应的方案数。

Solution

设 \(f[i][j][0/1]\) 表示对岸已经有 \(i\) 个 \(50\) 和 \(j\) 个 \(100\) 时最少的航行次数，\(g[i][j][0/1]\) 为对应的方案数

枚举本次走的 \(k,l\) 个数，利用组合数进行转移即可

最多转移 \(2n\) 轮一定能完事，复杂度 \(O(n^5)\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55;
const int dbg = 1;
const int mod = 1e9+7;

int n,m,a,b;
int f[N][N][2],g[N][N][2],nCr[N][N],e[N][N][2];

void readall()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        if(t==50) ++a;
        else ++b;
    }
}

void update(int a,int b,int &c,int &d,int &e)
{
    if(a<c)
    {
        c=a;
        d=b;
        e=1;
    }
    else if(a==c)
    {
        d+=b;
        d%=mod;
    }
}

void presolve()
{
    nCr[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        nCr[i][0]=1;
        for(int j=1;j<=i;j++)
        {
            nCr[i][j]=(nCr[i-1][j]+nCr[i-1][j-1])%mod;
        }
    }
}

void solve()
{
    memset(f,0x3f,sizeof f);
    f[0][0][0]=0;
    memset(g,0xff,sizeof g);
    g[0][0][0]=1;
    e[0][0][0]=1;
    for(int v=1;v<=2*n;v++)
    {
        for(int i=0;i<=a;i++)
        {
            for(int j=0;j<=b;j++)
            {
                for(int k=0;i+k<=a;k++)
                {
                    for(int l=0;j+l<=b;l++)
                    {
                        if(k==0&&l==0) continue;
                        if(k*50+l*100>m) continue;
                        update(f[i][j][0]+1,g[i][j][0]*nCr[a-i][k]%mod*nCr[b-j][l]%mod,f[i+k][j+l][1],g[i+k][j+l][1],e[i+k][j+l][1]);
                    }
                }
            }
        }
        for(int i=0;i<=a;i++)
        {
            for(int j=0;j<=b;j++)
            {
                for(int k=0;i-k>=0;k++)
                {
                    for(int l=0;j-l>=0;l++)
                    {
                        if(k==0&&l==0) continue;
                        if(k*50+l*100>m) continue;
                        update(f[i][j][1]+1,g[i][j][1]*nCr[i][k]%mod*nCr[j][l]%mod,f[i-k][j-l][0],g[i-k][j-l][0],e[i-k][j-l][0]);
                    }
                }
            }
        }
        if(f[a][b][1]<1e9)
        {
            cout<<f[a][b][1]<<endl<<g[a][b][1]<<endl;
            return;
        }
    }
    {
        cout<<-1<<endl<<0<<endl;
    }
}

signed main()
{
    readall();
    presolve();
    solve();
}

[CF295C] Greg and Friends - dp

原文：https://www.cnblogs.com/mollnn/p/13582648.html