【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

题解:

dp[i][j]表示以i为结尾,长度为j的不下降子序列数量


状态转移为:dp[i][j]+=dp[k][j-1];,枚举i之前所有比a[i]小的点k;

//
//  main.cpp
//
//
//  Created by Edwin on 2019/3/8.
//  Copyright &#169; 2019 Edwiv. All rights reserved.
//
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
const int maxn=500+10;
using namespace std;

int main(){
    int n,m;
    ll a[maxn];
    mst(a,0);
    sc2(n,m);
    FF(i,n){
        scanf("%lld",&a[i]);
    }
    ll dp[maxn][50];
    mst(dp,0);
    for(int i=0;i<n;++i){
        dp[i][1]=1;
        for(int j=2;j<=m;++j){
            for(int k=0;k<i;++k){
                if(a[k]<=a[i])
                    dp[i][j]+=dp[k][j-1];
            }
        }
    }
    ll ans=0;
    for(int i=0;i<n;++i)
        ans+=dp[i][m];
    printf("%lld\n",ans);
    return 0;
}

 

发表评论,支持MarkDown语法