[每日一题] 4.27 Removal
Removal
http://www.nowcoder.com/questionTerminal/114eb4af3edb4962ac2c2c4aadd73019
题意:
解法:
for(int i=1;i<=n;i++){ //枚举第i个数字前面i-m个位置,是否存在相同的数字 for(int j=i;j>=max(1,i-m);j--){ b[j] = (b[j]%mod + b[j-1]%mod - dp[j][a[i]] + mod)%mod; dp[j][a[i]] = b[j-1]; } }
时间复杂度:
std:
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 100005; ll dp[maxn][12],b[maxn]; int a[maxn]; const ll mod = 1e9 + 7; int main() { int n , m , k; b[0] = 1; while(~scanf("%d%d%d",&n,&m,&k)) { for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i] = 0; for(int j=1;j<=k;j++) dp[i][j] = 1ll*0; } for(int i=1;i<=n;i++){ for(int j=i;j>=max(1,i-m);j--){ b[j] = (b[j]%mod + b[j-1]%mod - dp[j][a[i]] + mod)%mod; dp[j][a[i]] = b[j-1]; } } printf("%lld\n",b[n-m]); } return 0; }
acm菜鸡日常 文章被收录于专栏
一般写一些打过的比赛题解以及不会的算法