性质：最终值域相同的一定是连续一段

花费最小？一定是值域个数个！并且当最后为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
     
      #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<
      
       using namespace std;typedef long long ll;template
       
        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
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}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]
           
            =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 "<
            <<" "<
             
              <<" "<
              
               <<" : "<
               
                <<" s "<
                
                 <