首页 > 代码库 > Codeforces Round #247 (Div. 2)

Codeforces Round #247 (Div. 2)

2024-07-06 18:08:32   232人阅读

A。水题。

遍历字符串对所给的对应数字求和即可。

B。简单题。

对5个编号全排列，然后计算每种情况的高兴度，取最大值。

C。dp。

设dp[n][is]表示对于k-trees边和等于n时，如果is==1表示存在边至少为d的边，如果is==0表示不存在边至少为d的边。

初始状态dp[0][0]=1。

//和为n且不存在至少为d的边的状态可以由所有不存在至少为d的边加一条小于d的边转移而来。

dp[n][0]=dp[n-1][0]+dp[n-2][0]+……+dp[n-(d-1)][0]

//和为n且存在至少为d的边的状态可以由 存在至少为d的边加一条小于d的边转移而来，无论是否存在至少d的边的状态加一条大于等于d的边 转移而来。

dp[n][1]=dp[n-1][1]+dp[n-2][1]+……+dp[n-(d-1)][0]+(dp[n-d][1]+dp[n-d][0])+(dp[n-(d+1)][1]+dp[n-(d+1)][0])+……+(dp[n-(d+1)][1]+dp[n-(d+1)][0])+……+(dp[n-k][1]+dp[n-k][0])

这个题状态设计的很巧妙，可以很好的降低时间复杂度。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#define mod 1000000007
#define ll long long
using namespace std;
ll dp[105][105];
int n,k,d;
int main()
{
    cin>>n>>k>>d;
    dp[0][0]=1;
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<d&&i-j>=0; ++j)
        {
            dp[i][0]+=dp[i-j][0];
            dp[i][0]%=mod;
        }
        for(int j=1; j<=k&&i-j>=0; ++j)
        {
            if(j<d)
                dp[i][1]+=dp[i-j][1];
            else
                dp[i][1]+=dp[i-j][1]+dp[i-j][0];
            dp[i][1]%=mod;
        }
    }
    cout<<dp[n][1]<<endl;
    return 0;
}
View Code

 


联系
我们