D古韵之乞巧【noip模拟赛1】

发表于 | 分类于 ， | 阅读量 次

描述

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

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

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

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

——祖咏《七夕》

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

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

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

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

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

输入

第一行有两个整数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

来源：
来自 <http://www.dingbacode.com/contest/19/problem/D>

题解：
dp

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

long long f[105][25];
long long a[105];

int main()
{

    long long n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i];

    for(int i=1; i<=n; i++)
        f[i][1]=1;

    for(int i=1; i<=n; i++)
        for(int k=2; k<=m; k++)
            for(int j=1; j<=i-1; j++)
                if(a[i]>a[j])
                    f[i][k]=f[i][k]+f[j][k-1];
    long long ans=0;
    for(int i=1; i<=n; i++)
        ans+=f[i][m];
    cout<<ans<<endl;

    return 0;
}