ARC 128D - Neq Neq(dp+组合数学+思维)E . Tutorial Groupings (DP + 思维)

简介: 【6月更文挑战第15天】

链接

题意:

给出你一个长度为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;
}
AI 代码解读

题意:

给出你N个数,然后让你分组,每组中最多有s个元素,并且要求整个序列严格递增,也就是$TiT{i+1}k$.问方案数?对1e9+7取模。

分析:

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

两种情况 :

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

  • 然后我们再看j!=1dp[i][j]肯定是从dp[i1][j1],接着上一次的增加一个,如果能放下就接手上一个状态就好了,不能就说明到不了。
    能不能放下取决于是否满足:这一组内极差是否小于等与k。也就是最大最小的差是否符合条件。如果符合条件:dp[i][j]=dp[i1][j1];如果不符合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;
    }
    
    AI 代码解读
iamzfh
+关注
目录
打赏
0
1
1
0
48
分享
相关文章
算法专题1——动态规划 Dynamic Programming,DP
算法专题1——动态规划 Dynamic Programming,DP
111 0
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
252 0
codeforces118——D. Caesar‘s Legions(DP)
codeforces118——D. Caesar‘s Legions(DP)
108 0
codeforces118——D. Caesar‘s Legions(DP)
codeforces319——B. Psychos in a Line(思维+单调栈)
codeforces319——B. Psychos in a Line(思维+单调栈)
112 0
codeforces319——B. Psychos in a Line(思维+单调栈)
Codeforces1499——C. Minimum Grid Path(思维+分奇偶+贪心)
Codeforces1499——C. Minimum Grid Path(思维+分奇偶+贪心)
111 0
codeforces859——C. Pie Rules(思维+DP)
codeforces859——C. Pie Rules(思维+DP)
120 0
动态规划dp(三个案例详解)
动态规划dp(三个案例详解)
253 0
[leetcode] 798 得分最高的最小轮调 - 思维dp
轮调实际上是这个样子的: 每次讲最前面的元素放到数组最后,然后将所有元素集体向前移动一位 在当前值a [ i ] ≤ i 的时候会获得1 分,问最大的分是多少? 先说明一个事实: 一次轮调之后,对于除了最前面的每个数,他的下标会减小1 ,而对于最前面的那个数,他的下标直接变为最大 大致分为以下三种情况: 本来a [ i ] 就小于下标i ,轮调之后下标减小值不变,所以依旧会获得1 分 本来a [ i ] = = i ,轮调之后,下标减小而值不变,所以值就比下标大1 ,所以说会失去1 分 本来a [ i ] > i,轮调之后,下标更小,值依旧会大于下标,所以依旧不得分
139 0
[leetcode] 798 得分最高的最小轮调 - 思维dp
【动态规划 / 总结必看】从一道入门题与你分享关于 DP 的分析技巧 ...|刷题打卡
【动态规划 / 总结必看】从一道入门题与你分享关于 DP 的分析技巧 ...|刷题打卡
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等