每日一题(牛客) — 2020 - 04 - 27
dp题,自己对于dp虽然说没具体学过,但是还是知道一些的,虽然这题肯定是不会做的,甚至没想到用dp(又可以学到新知识了)
解题思路:
- 首先是一个串中删除一些位置,让剩下的串不同,问有多少种
- 对于这方面的题,没有很好的理解,主要是想不出是dp,看了一些大佬的题解,然后跟着敲才会的。
- 首先dp[i][j] 表达的是前 i 个位置,删除 j 个,有多少个不同,那么我们的转移方程还是比较简单的dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j])%mod,但是现在的问题就是去重,就是我们可能删除一些不同的,但是我们的结果是相同的,这就是重复的,比如 1 2 3 1,我们删除 1 2 3 和删除 2 3 1 是一样的
- 所以我们考虑去重的话首先要证明当前点的值存在前一个值,而且前一个值于当前值的距离(i - last[i]) <= j,这里 j 是需要删除的个数。
- 然后我们进行赋初值,dp[i][0] 肯定都是1,dp[i][i]的话也是 1,主要是因为空。
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int N = 100010; const int mod = 1e9 + 7; long long last[N]; long long c[N]; long long a[N]; long long dp[N][15]; int main(){ int n, m, k; while(scanf("%d%d%d",&n,&m,&k) != EOF){ memset(last, 0, sizeof last); memset(c,0,sizeof c); for (int i = 1; i <= n; i++){ scanf("%lld",&a[i]); last[i] = c[a[i]]; c[a[i]] = i; } for (int i = 0; i <= n; i++) dp[i][0] = dp[i][i] = 1; for (int i = 1; i <= n; i++){ for (int j = 1; j <= min(i - 1, m); j++){ dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod; if (last[i] != 0 && i - last[i] <= j){ dp[i][j] = (dp[i][j] - dp[last[i] - 1][j - (i - last[i])] + mod) % mod; } } } printf("%lld\n",dp[n][m]); } return 0; }