每日一题-NC17137-DP

题目链接

NC17137

思路

DP状态定义为dp[i][j]表示前i个数删除j个后的答案。那么很容易得到递推方程

dp[i][j]=dp[i-1][j-1]+dp[i-1][j];

就是删除当前这个和不删除当前这个的情况，然后如果是 1 2 3 5 6 7 8 5 m=4的话，就会出现删除5 6 7 8 和删除6 7 8 5的情况重复的情况，我们需要减去重复的这部分，观察到重复的这部分需要把6 7 8给删除，就是把两个5之间的数全给删除了，于是重复的这部分就是dp[pos-1][j-(i-pos)]就代表中间的全部给删除了。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 1e5+10;
int dp[N][15],pos[15];
const int mod = 1e9+7;
int main(){
	int n,m,k;
	while(cin>>n>>m>>k){
		memset(dp,0,sizeof(dp));
		memset(pos,0,sizeof(pos));
		dp[0][0]=1;
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			dp[i][0]=1;
			for(int j=1;j<=min(m,i);j++){
				dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
				if(pos[x]&&j-i+pos[x]>=0){
					dp[i][j]=(dp[i][j]-dp[pos[x]-1][j-i+pos[x]]+mod)%mod;
				}
			}
			pos[x]=i;
		}
		printf("%dn",dp[n][m]);
	}
}

最后

以上就是俊秀万宝路为你收集整理的每日一题-NC17137-DP的全部内容，希望文章能够帮你解决每日一题-NC17137-DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。