https://ac.nowcoder.com/acm/contest/139/E 题 意 ： 从 给 定 n 个 数 的 数 组 中 删 除 m 个 数 ， 问 组 成 的 新 数 组 的 种 类 数 题意：从给定n个数的数组中删除m个数，问 组成的新数组的种类数 题意：从给定n个数的数组中删除m个数，问组成的新数组的种类数 题 解 ： n < = 1 e 5 , m < = 10 ， 想 到 d p 题解：n<=1e5,m<=10，想到dp 题解：n<=1e5,m<=10，想到dp d p [ i ] [ j ] 表 示 从 前 i 个 数 中 删 除 j 个 数 的 种 类 数 ， dp[i][j] 表示从前i个数中删除j个数的种类数， dp[i][j]表示从前i个数中删除j个数的种类数， 很 容 易 想 到 ， 如 果 当 前 位 不 删 除 ， 那 么 方 案 数 就 是 d p [ i − 1 ] [ j − 1 ] ， 如 果 删 除 ， 方 案 数 就 是 d p [ i − 1 ] [ j ] 很容易想到，如果当前位不删除，那么方案数就是dp[i-1][j-1]，如果删除，方案数就是dp[i-1][j] 很容易想到，如果当前位不删除，那么方案数就是dp[i−1][j−1]，如果删除，方案数就是dp[i−1][j] 转 移 方 程 就 是 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i − 1 ] [ j − 1 ] 转移方程就是 dp[i][j] = dp[i-1][j] + dp[i-1][j-1] 转移方程就是dp[i][j]=dp[i−1][j]+dp[i−1][j−1]
猛 敲 一 发 发 现 样 例 都 过 不 了 ， 问 题 就 出 在 这 个 转 移 方 程 会 出 现 重 复 的 情 况 猛敲一发发现样例都过不了，问题就出在这个转移方程会出现重复的情况 猛敲一发发现样例都过不了，问题就出在这个转移方程会出现重复的情况 比 如 2312312 ， i = 6 ， j = 3 ， 假 若 删 除 i = 4 到 i = 6 ， 那 么 数 列 变 成 2312 ， 那 么 我 们 发 现 当 i = 3 ， j = 3 时 ， 我 们 删 除 了 i = 1 到 i = 3 ， 比如 2 3 1 2 3 1 2， i=6，j=3，假若删除i=4到i=6，那么数列变成2 3 1 2，那么我们发现当i=3，j=3时，我们删除了i=1到i=3， 比如2312312，i=6，j=3，假若删除i=4到i=6，那么数列变成2312，那么我们发现当i=3，j=3时，我们删除了i=1到i=3， 结 果 变 成 了 2312 ， 与 i = 6 时 的 结 果 重 复 ， 问 题 就 在 于 相 同 的 数 字 在 之 前 的 方 案 计 算 中 就 已 经 对 答 案 有 贡 献 了 结果变成了2 3 1 2，与i=6时的结果重复，问题就在于相同的数字在之前的方案计算中就已经对答案有贡献了 结果变成了2312，与i=6时的结果重复，问题就在于相同的数字在之前的方案计算中就已经对答案有贡献了 这 里 设 置 一 个 数 组 p r e [ i ] 表 示 i 这 个 位 置 的 数 a [ i ] ， 它 前 一 次 出 现 的 位 置 。 每 次 d p 的 时 候 只 需 要 在 原 有 方 程 的 基 础 上 减 去 前 一 次 出 现 的 位 置 前 的 方 案 数 就 是 答 案 。 这里设置一个数组pre[i]表示i这个位置的数a[i]，它前一次出现的位置。 每次dp的时候只需要在原有方程的基础上减去前一次出现的位置前的方案数就是答案。 这里设置一个数组pre[i]表示i这个位置的数a[i]，它前一次出现的位置。每次dp的时候只需要在原有方程的基础上减去前一次出现的位置前的方案数就是答案。
#include<iostream> #include<algorithm> #include<cstdio> #include<stdio.h> #include<string.h> #include<queue> #include<cmath> #include<map> #include<set> #include<vector> using namespace std; #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define mem(a,b) memset(a,b,sizeof(a)); #define lowbit(x) x&-x; #define debugint(name,x) printf("%s: %d\n",name,x); #define debugstring(name,x) printf("%s: %s\n",name,x); typedef long long ll; typedef unsigned long long ull; const double eps = 1e-6; const int maxn = 1e5+5; const int mod = 1e9+7; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,k; ll dp[maxn][15]; int pre[maxn],a[maxn],num[maxn]; int main() { while(~scanf("%d%d%d",&n,&m,&k)){ mem(pre,-1); mem(num,0); for(int i = 1; i <= n; i++){ scanf("%d",&a[i]); if(pre[i] == -1){ pre[i] = 0; } if(!num[a[i]]){ num[a[i]] = i; }else{ pre[i] = num[a[i]]; num[a[i]] = i; } } mem(dp,0); dp[0][0] = 1; for(int i = 1; i <= n; i++){ dp[i][0] = 1; for(int j = 1; j <= m; j++){ dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] - dp[pre[i]-1][j-(i-pre[i])] + mod)%mod; } } ll ans = 0; printf("%lld\n",dp[n][m]%mod); } }