牛客多校Round 1

墨蓝 2021-10-26 12:31 226阅读 0赞

Solved:1

rank:249

E. Removal

dp i,j表示前i个数删除了j个且选择了第i个的答案

类似字符串的dp 预处理一下nex i\_k即i后面k第一次出现的位置  就好转移了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll mod = 1e9 + 7;
    
    int s[100005];
    int nex[100005][12];
    int now[12];
    ll dp[100005][12];
    
    int main()
    {
        int n, m, kk;
        while(~scanf("%d%d%d", &n, &m, &kk))
        {
            memset(dp, 0, sizeof(dp));
            for(int i = 1; i <= n; i++) scanf("%lld", &s[i]);
            for(int i = 1; i <= kk; i++) now[i] = n + 1;
            
            for(int i = n; i >= 0; i--)
            {
                for(int j = 1; j <= kk; j++) nex[i][j] = now[j];
                now[s[i]] = i;
            }
            
            dp[0][0] = 1; //dp[0][0] = 1;
            for(int i = 0; i <= n; i++)
            {
                for(int j = 0; j <= m; j++)
                {
                    if(!dp[i][j]) continue;
                    for(int k = 1; k <= kk; k++)
                    {
                        int t = nex[i][k];
                        if(t == n + 1) continue;
                        if(t - i + j - 1 > m) continue;
                        (dp[t][t - i + j - 1] += dp[i][j]) %= mod;
                    } 
                }
            }
            
            ll ans = 0;
            for(int i = 1; i <= n; i++)
                if(i - n + m >= 0)
                    (ans += dp[i][i - n + m]) %= mod;
            printf("%lld\n",  ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/lwqq3/p/9344596.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211026/219a6dd43515489091050eb64eb5595b.png