鏈接：

時間限制：C/C++ 2秒，其他語言4秒 空間限制：C/C++ 524288K，其他語言1048576K 64bit IO Format: %lld

題目描述

Bobo has a sequence of integers s1, s2, …, sn where 1 ≤ si ≤ k. Find
out the number of distinct sequences modulo (109+7) after removing
exactly m elements.

輸入描述:

The input consists of several test cases and is terminated by
end-of-file. The first line of each test case contains three integers
n, m and k. The second line contains n integers s1, s2, …, sn.

輸出描述:

For each test case, print an integer which denotes the result.

示例1
輸入

3 2 2 1 2 1 4 2 2 1 2 1 2

輸出

2 4

題意：

長度為n的一組數(shù)，每個數(shù)都大于等于1，小于等于k，現(xiàn)在刪除里面m個數(shù)，問會出現(xiàn)多少種情況？

題解：

dp問題
dp[i][j]表示前i個數(shù)字刪去j個數(shù)字之后有多少個不同的序列數(shù)
列出轉(zhuǎn)移方程：f [ i ] [ j ] = f [ i - 1 ] [ j ] + f [ i - 1 ] [j - 1]
轉(zhuǎn)移方程很經(jīng)典，就是我們考慮當前這個數(shù)刪不刪，如果不刪，那就是前i-1個數(shù)刪去j個數(shù)，如果刪去，那就是前i-1個數(shù)刪去j-1個數(shù)
但是！但是！
這個題會出現(xiàn)重復(fù)情況
比如：513241
刪去四個數(shù)，有可能是51也可能是51（*為被刪去的數(shù)）
，這不就重復(fù)了
怎么去除重復(fù)？
發(fā)生重復(fù)說明當前這個第i位的w選上了，我們需要找上一個出現(xiàn)的w，如果以w結(jié)尾并且子串的長度和刪后長度（i-j）相等的就是和dp[ i ] [ j ] 重復(fù)的，直接減去即可.
為什么呢？繼續(xù)看我給的樣例：… 5 1 3 2 4 1
先不管5之前的省略號，假設(shè)5是第一位
我們知道第二位和第六位都是1，兩個i之間的距離是len=5（含兩端），如果我們將兩個1之間的數(shù)全部刪去，就是5 1 * * * 1，再刪除任何一個1，剩下的數(shù)就是重復(fù)的，你刪去前面的1，剩下5 * * * * 1，刪除后面剩下5 1 * * * * 。所以重復(fù)的部分就是第一個1前面的數(shù)與1所組成的序列 。
加上省略號，5之前還有很多數(shù)，查重的話就是把省略號中（算上5）的方法數(shù)去掉
我們要用到：last[i]表示第i位的數(shù)w的上一次出現(xiàn)位置
能得到：
dp [ i ] [ j ] = d p [ i ] [ j ]? dp [ pre [ i ] ? 1 ] [ j? ( i ? pre [ i ] ) ]
dp [ pre [ i ] ? 1 ] [ j? ( i ? pre [ i ] ) ] ：就是重復(fù)情況
pre[i] - 1就是重復(fù)的數(shù)字上一次出現(xiàn)的位置的前一位
（i - pre [ i ] ）就是len-1，就是兩個數(shù)之間的數(shù)全刪去再加上刪任意一個端點。
j-（len-1）就是把這些數(shù)刪去后，還要刪的數(shù)量，而要刪的就是pre[i]-1之前的數(shù)
我可能講的不是很明白，看代碼吧

代碼：

#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 2; const int mod= 1e9+7; int dp[maxn][12]; int a[maxn]; int pos[12], last[maxn]; void init() {for (int i = 0; i <= n; i++)dp[i][0] = dp[i][i] = 1; } int main() {int n, m, k,w;while (~scanf("%d%d%d",&n,&m,&k)){init();//初始化，不刪去和全刪去的都只有一種 memset(pos, 0, sizeof(pos));for (int i = 1; i <= n; i++) {scanf("%d",&a[i]);last[i] = pos[a[i]];pos[a[i]] = i;}for (int i = 1; i <= n; i++) {w = min(i - 1, m);for (int j = 1; j <= w; j++){dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;//不查重的情況 if (last[i] && i - last[i] <= j)//如果前面有重復(fù)的數(shù)字，并且所要刪除的數(shù)字的數(shù)量要能夠刪去重復(fù)數(shù)字之間的數(shù)（加上一端重復(fù)的數(shù)）dp[i][j] = (dp[i][j] - dp[last[i] - 1][j - (i - last[i])] + mod) % mod;//將重復(fù)部分去掉}}cout << dp[n][m] << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【每日一题】4月27日题目精讲 Removal的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。