【noip模拟赛1】古韵之乞巧 （dp）

时间：2023-03-08 15:38:04

描述

闺女求天女，更阑意未阑。

玉庭开粉席，罗袖捧金盘。

向月穿针易，临风整线难。

不知谁得巧，明旦试相看。

——祖咏《七夕》

女子乞巧，是七夕的重头戏。古时，女子擅长女红被视为一种重要的德行。所以女孩子们纷纷在七夕这天祈求上天，是自己变得更加灵巧。仰头凝视，以虔诚的心去膜拜桂魄；双手合十，用坚定信念去盼望未来，祈求能有更出众的才能。一根针、一丝线、一轮月、一束影，组成了一个简单的乞巧仪式。

“年年岁岁花相似，岁岁年年人不同。”千百年后的今天，女孩子们更加看重自己的才华与能力。韵哲君参加了一个新乞巧活动：

韵哲君发现自己的面前有一行数字，当她正在琢磨应该干什么的时候，这时候，陈凡老师从天而降，走到了韵哲君的身边，低下头，对她耳语了几句，然后飘走了。

陈凡老师说了什么呢，且听下回分解。

接上回书，陈凡老师原来对韵哲君说了这些话：“还记得我传授给你的不下降子序列吗？你现在只要找出一定长度的不下降子序列的种数，你就完成任务了。”

输入

第一行有两个整数N(0<N<=100)，M(0<M<=20)；

N表示给出多少个整数，M表示给出的定长；

第二行有N个整数，对于每个数字(-10000<=T[i]<=10000)。

输出

输出一个整数，在给出的数列中定长不下降子序列的种数。

输入样例 1

10 5

1 2 3 4 5 6 7 8 9 10

输出样例 1

252

dp[i][j] 表示处理前i个数字   长度为j的不下降子序列的个数

先是参考了最长不下降子序列的个数：   n^2 写法：
long long dp[N];

int a[N];

int main()

{

   int n;cin>>n;

   for(int i=;i<=n;i++)

    RI(a[i]);

   int ans=;

   for(int i=;i<=n;i++)

   {

       for(int j=;j<i;j++)

        if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+ );

       ans=max(ans,dp[i]);

   }

   cout<<ans;

}

最长不下降子序列个数


将所有满足的情况累合起来
#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<queue>

using namespace std;

//input

#define RI(n) scanf("%d",&(n))

#define RII(n,m) scanf("%d%d",&n,&m);

#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)

#define RS(s) scanf("%s",s)

#define LL long long

#define REP(i,N)  for(int i=0;i<(N);i++)

#define CLR(A,v)  memset(A,v,sizeof A)

//////////////////////////////////

#define N 2050

#define inf -0x3f3f3f3f

long long dp[N][N];

int a[N];

int main()

{

   int n,m;

   RII(n,m);

   for(int i=;i<=n;i++)

    RI(a[i]);

   CLR(dp,);

   for(int i=;i<=n;i++)

    dp[i][]=;//先初始化 每个数字都是长度为1的序列

   for(int i=;i<=n;i++)

       for(int k=;k<=m;k++)

        for(int j=;j<=i-;j++)

          if(a[i]>=a[j])dp[i][k]+=dp[j][k-];//遍历完之后 显然dp[i][k]所有子序列必定包含a[i]（且a[i]为最后一个数）  以此类推之前的dp[j]也都是以a[j]为最后一个数  所以不会有重复  

   long long ans=;

   for(int i=;i<=n;i++)

    ans+=dp[i][m];

   printf("%lld\n",ans);

}






相关文章