题目大意:
给定一个序列, 移除m个字母后, 问可以形成多少个不同的序列
思路:
- 正常想法: dp[i][j], 到第i个时, 移除m个后,有多少个不同的字符串
- 转移: dp i j-1 (移除自己) (注意题目问的是移除后,有多少个不同的子串, 此时移除自己时, 会有重复的情况) dp i-1 j, 不移除自己
- 重复的情况是: 2个相同的数, 中间都被删掉了,自己也要删掉, 就 - 去 上一个数出现的位置 时的该有的dp情况
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1e5+100, mod = 1e9+7; int n, m, k, s[maxn]; long long dp[maxn][20]; int pre[maxn]; int prex[20]; int main() { while(scanf("%d%d%d", &n, &m, &k) == 3) { memset(dp, 0, sizeof(int)*20*(n+1)); memset(prex, 0, sizeof(prex)); for(int i=1; i<=n; ++i) { scanf("%d", &s[i]); pre[i] = prex[s[i]]; prex[s[i]] = i; } dp[0][0] = 1; for(int i=1; i<=n; ++i) { dp[i][0] = 1; int d = i - pre[i]; for(int j=1; j<=m&&j<=i; ++j) { dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; if(pre[i] && d<=j) dp[i][j] -= dp[pre[i]-1][j-d]; ///dp[i][j] %= mod; dp[i][j] += mod; dp[i][j] %= mod; } } printf("%lld\n", dp[n][m]); } return 0; }
后记:
- 注意看 dp要的内容是什么
- 在更新的时候思考有没有重复的情况
- 有重复情况,就把他减掉, 不要放弃