链接

题意：

给出你一个长度为n的序列，你可以对其操作使得这个序列发生变化，问一共有多少种？

• 对于连续的i-1,i,i+1，这三个数如果满足 $a{i-1}!=a{i}$并且$a{i}!=a{i+1}$ 那么我们就可以将$a_i$删掉。

  分析:

  明显看出利用DP来解决组合数学问题。
  那么我们认为第$i$位置，表示到i有dp[i]种方案数。
  那么他会从那种状态转移过来那？
  首先dp[i]是继承dp[i-1]，这一点是一定的，其次他还可以通过删除前一个元素，就是看看i-2,i-1,i是否符合前面说的条件，那么dp[i]+=dp[i-2],
  还有就是除了前面一个，我们也想知道删除前面一个或者多个，那么我们用前缀维护即可，但是前缀维护到同时出现同一个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;

const int MOD = 998244353;
const int mod = 1e9 + 7;
const int MAX = 2e5 + 10;
const int dx[] = {
   0, 1, -1, 0, 0};
const int dy[] = {
   0, 0, 0, 1, -1};
const int dz[] = {
   1, -1, 0, 0, 0, 0 };
int day[] = {
   0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};


void init()
{
   

}
ll qpow(ll a, ll b, ll p)
{
   
    ll ans = 1;
    while(b)
    {
   
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}


string str;
ll n,m,s;
ll a[MAX],dp[MAX],b[MAX],sum[MAX];
void solve()
{
   
    cin>>n;
    dp[0]=1;
    ll j=0,num=0,k=1;
    for(int i=1;i<=n;i++){
   
        cin>> a[i];
        dp[i]=dp[i-1];/// 继承上一状态
        if(a[i]==a[i-1]) j= i-1;///上一个 一对相等的位置，
        if(i>2&&a[i]!=a[i-1]&&a[i-1]!=a[i-2])///满足条件
        {
   
            dp[i]=(dp[i]+dp[i-2])%MOD;
        }
        if(b[a[i]]==0) num++;///来了一个新元素
        b[a[i]]++;
        while(k<i-2 && num>=3){
   
            b[a[k]]--;
            if(b[a[k]]==0)num--;
            k++;
        }
        if(j<k) dp[i]+=sum[k-1]-sum[j];
        dp[i]=(dp[i]%MOD+MOD)%MOD;
        sum[i]=(sum[i-1]+dp[i])%MOD;
    }
    cout<<dp[n]<<endl;

}

int main()
{
   
    init();
    ll t = 1;
    ///scanf("%lld", &t);
    while(t--)
    {
   
        solve();
    }
    return 0;
}

题意：

给出你$N$个数,然后让你分组，每组中最多有$s$个元素，并且要求整个序列严格递增，也就是$Ti$组最大的元素严格小于$T{i+1}$中最小的元素。并且一个组中极差最大为$k$.问方案数？对1e9+7取模。

分析：

首先我们看数据范围 n为$10000$ ,s为$100$，
那么我们可以用$dp[i][j]$表示第i个位置，以长度为j为一组结束的方案数。

两种情况 :

• $j=1$.那么我们可以想到$dp[i][1]$表示第i个位置，他自己为一组结束，他可以从何种状态转移过来那？他可以从 $dp[i-1][1],dp[i-1][2]......dp[i-1][s]$转移过来，就相当于另起炉灶。

• 然后我们再看$j!=1$，$dp[i][j]$肯定是从$dp[i-1][j-1]$,接着上一次的增加一个，如果能放下就接手上一个状态就好了，不能就说明到不了。
  能不能放下取决于是否满足：这一组内极差是否小于等与k。也就是最大最小的差是否符合条件。如果符合条件：$dp[i][j]=dp[i-1][j-1];$如果不符合$dp[i][j]=0;$

  ///苟利国家生死以，岂因祸福避趋之。
  #include <bits/stdc++.h>
  using namespace std;
  #define ll long long
  const int maxn = 2e5 + 7;
  const int mod = 1e9 + 7;
  const double pi = 3.14159265358979;
  ll n,k,s;
  ll a[maxn];
  ll dp[20000][200];
  ll sum;
  int main()
  {
       
    cin >> n >> k >> s;
    for(int i = 1; i <= n; i++)
    {
       
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
  
    for(int i = 1; i <= n; i++) dp[i][1] = 1;    
    ///直接dp[1][1]=1也行。
    for(ll i = 2; i <= n; i++)
    {
       
        sum=0;
        for(ll j=1;j<=s;j++) sum+=dp[i-1][j],sum%=mod;
  
        dp[i][1]=sum;
  
        for(ll j=2;j<=min(i,s);j++){
       ///j 是i位置长度 那么 i-1位的长度为j-1
            if(a[i]-a[i-j+1]<=k){
       
                dp[i][j]=dp[i-1][j-1];
            }else {
       
                dp[i][j]=0;
            }
        }
    }
    sum=0;
    for(int i=1;i<=s;i++){
       
        sum+=dp[n][i];
        sum%=mod;
    }
    cout<<sum<<endl;
    return 0;
  }