【每日一题】Removal(4.27)

dp计数问题
先考虑简单一点的情况，如果允许重复的话，可以用dp[i][j]表示当前位置为i，并且删除了j个元素后的方法数，那么转移相当于考虑第i个位置的数选和没选两种情况，即dp[i][j] = dp[i-1][j] + dp[i-1][j-1],从i=1到n扫描一遍就可以得到答案了。
这道题要求不重复，如果用dp[i][j]表示当前位置为i，删除了j个元素后不重复的方法数，怎么转移呢？
如果还用dp[i][j] = dp[i-1][j-1]可能会引起重复，思考下引起重复的原因肯定是第i个位置的数选中，

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e5+7;
const int mod = 1e9+7;
int a[maxn],dp[maxn][11],l[11];    //l记录上一次出现的位置


int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,k;
    while(cin>>n>>m>>k)
    {
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=0;i<=11;i++) dp[i][i] = 1;   //全删除
        for(int i=1;i<=n;i++) dp[i][0] = 1;   //删除0个元素
        memset(l,0,sizeof(l));


        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=min(i-1,m);j++)
            {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%mod;

                int len = i-j;            //字串的长度
                if(l[a[i]])
                {
                    int pos = l[a[i]];
                    int cnt = pos -len;     //要删除的元素的个数
                    if(cnt>=0)
                        dp[i][j] = (dp[i][j]-dp[pos-1][cnt]+mod)%mod;

                }

            }
            l[a[i]] = i;

        }

        cout<<dp[n][m]<<'\n';
    }


    return 0;
}