hihoCoder挑战赛25

萌新第一次打hihoCoder的比赛有点慌

T1并不是特别难想到dp就好做了

显而易见的是一个01背包问题

Code：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int INF=;

int n,m,i,j,k,f[],son[],x;

int main()

{

    cin>>n;memset(son,,sizeof son);

    for (int i=;i<n;i++) cin>>x,son[x]++;

    memset(f,INF,sizeof f);f[]=;

    for (int i=;i<=n;i++)

        for (int j=n;j>=son[i];j--)

            f[j]=min(f[j],f[j-son[i]]+);

    for (int i=;i<n;i++)

    {

        if (f[i]>n) cout<<-<<" ";

        else cout<<f[i]<<" ";

    }

    return ;

}

T2的话是一个区间dp的题

可以抽象成在某一棵子树上维护方案数

在维护两个数组f,g

g[i]表示这棵子树到i点的方案数

f[i][j]表示[i,j]为一颗子树的方案数

Code：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MOD 998244353

using namespace std;

long long n,g[],f[][];

char A[],B[];

int main()

{

    cin>>n;getchar();gets(A+);gets(B+);

    for (int i=;i<=n;i++)

        if (A[i]!='') f[i][i]=;

    for (int i=n-;i>=;i--)

        if (A[i]!='')

        {

            for (int j=i;j<=n;j++) g[j]=;

            g[i]=;

            for (int j=i+;j<=n;j++)

                for (int k=j;k<=n;k++)

                {

                    if (B[j]!='') g[k]=(g[k]+(long long)f[j][k]*g[j-])%MOD;

                    if (B[j]!='') f[i][k]=(f[i][k]+(long long)f[j][k]*g[j-])%MOD;

                }

        }

    if (B[]=='') cout<<<<endl;

    else cout<<f[][n]<<endl;

}

T3，T4尚未写好，以后再更

秒客网

hihoCoder挑战赛25

相关文章