性质：最终值域相同的一定是连续一段
花费最小？一定是值域个数个！并且当最后为i的数恰好只有i一个位置的时候，肯定选择不动，少花费一个
所以，我们考虑：每个最终方案在花费最小的方案下恰好被统计一次！
而对于一个合法的最终序列，考虑是怎样构造的
一定是先构造小的数，填充一些区间，再用大的数，可能覆盖一些小数的区间
换句话说，只要每个数的能填充这一段区间，就是合法的
也就是这个区间不能存在比这个数大的数！
有了这个发现，DP状态和转移就容易设计了
连续一段好处理，但是怎么知道之前没有出现过这个数？
还和位置有关，所以考虑顺序DP，到了i位置，考虑a[i]在最终序列的出现情况
f[i][j][k]考虑完了前i个位置，最终序列确定了前j个，花费k次
1.f[i-1][i-1][k]->f[i][i][k]i单独一块，不花费
2.f[i-1][j'][k-1]->f[i][j][k]把[j'+1,j]都变成a[i]，前提是[j'+1,j]没有比a[i]大的，可以提前找到[l,r]极大的区间都<=a[i]
特别地，当j=i的时候，j'<j-1，否则白白花费一个代价，不满足“每个最终方案在花费最小的方案下恰好被统计一次！”，我们在第一个转移考虑了，这样会算重
3.f[i-1][j][k]->f[i][j][k]，a[i]这个数不会出现在值域集合内。直接覆盖
第2个用前缀和优化即可
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Miracle{ const int N=202; const int mod=1e9+7; int n,m; int f[N][N][N],s[N][N][N]; int a[N]; int ad(int x,int y){ return x+y>=mod?x+y-mod:x+y; } void clear(){ memset(f,0,sizeof f);memset(s,0,sizeof s); } int main(){ int t;rd(t); while(t--){ clear(); rd(n);rd(m); for(reg i=1;i<=n;++i) rd(a[i]); f[0][0][0]=1; for(reg j=0;j<=n;++j) s[0][j][0]=1; for(reg i=1;i<=n;++i){ int l=i,r=i; while(l>1&&a[l-1]<a[i]) --l; while(r<n&&a[r+1]<a[i]) ++r; // cout<<" i "<<i<<" : "<<l<<" and "<<r<<endl; for(reg k=0;k<=m;++k){ f[i][i][k]=ad(f[i][i][k],f[i-1][i-1][k]); for(reg j=0;j<=n;++j){ if(l<=j&&j<=r){ if(j==i){ if(j-2>=0&&l-2>=0) f[i][j][k]=ad(f[i][j][k],ad(s[i-1][j-2][k-1],mod-s[i-1][l-2][k-1])); else if(j-2>=0) f[i][j][k]=ad(f[i][j][k],s[i-1][j-2][k-1]); }else{ f[i][j][k]=ad(f[i][j][k],ad(s[i-1][j-1][k-1],l-2>=0?mod-s[i-1][l-2][k-1]:0)); } } f[i][j][k]=ad(f[i][j][k],f[i-1][j][k]); } } for(reg k=0;k<=m;++k){ for(reg j=0;j<=n;++j){ s[i][j][k]=f[i][j][k]; if(j) s[i][j][k]=ad(s[i][j][k],s[i][j-1][k]); } } } // for(reg i=0;i<=n;++i){ // for(reg j=0;j<=n;++j){ // for(reg k=0;k<=m;++k){ // // cout<<" i j k "<<i<<" "<<j<<" "<<k<<" : "<<f[i][j][k]<<" s "<<s[i][j][k]<<endl; // } // } // } ll ans=0; for(reg k=0;k<=m;++k) ans=ad(ans,f[n][n][k]); printf("%lld ",ans); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */