Description
最初你有一个长度为 N 的数字序列 A。为了方便起见,序列 A 是一个排列。 你可以操作最多 K 次。每一次操作你可以先选定一个 A 的一个子串,然后将这个子串的数字全部变成原来这个子串的最大值。问最终有几种可能的数字序列。答案对 1e9+7 取模。
Input
第一行两个数 N 和 K。第二行 N 个数,描述一个排列 A。 N,K<=500, 有6组数据N>100,有梯度
Output
输出一个数,表示答案在模域下的值。
Sample Input
3 2
3 1 2
Sample Output
4
题解:
我太水了,连普及组的题目都看了题解。 这个题目,我们考虑对于每个点,算出他向左,向右最多可以延伸多少,然后我们就可以把他看成一个区间,然后我们有m次机会使得这个区间出现,如果什么都没有发生改变,也就没有用这次的机会,所以我们可以得到一个状态,dp[i][j]表示已经覆盖到了i,用了j次机会的方案数。然后转移就比较简单了。 代码:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define mod 1000000007
#define ll long long
using namespace std;
ll dp[510][510],v[510];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&v[i]);
dp[0][0]=1;
for(int i=1;i<=n;i++){
int l,r;
for(l=i;l>1&&v[l-1]<v[i];l--);
for(r=i;r<n&&v[r+1]<v[i];r++);
for(int j=m;j>=0;j--){
ll sum=0;
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
if(j){
for(int k=l;k<=r;k++) sum=(sum+dp[k-1][j-1])%mod,dp[k][j]=(dp[k][j]+sum)%mod;
dp[i][j]=(dp[i][j]-dp[i-1][j-1]+mod)%mod;
}
}
}
ll ans=0;
for(int i=0;i<=m;i++) ans=(ans+dp[n][i])%mod;
printf("%lld",ans);
return 0;
}
转载于:https://www.cnblogs.com/renjianshige/p/7716686.html