Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

BCACM11G - Dãy con tăng dần tự nhiên bậc K

Cho dãy gồm N số phân biệt AN = {a1, a2, .., aN } và số tự nhiên K (K<=N<=100). Ta gọi một dãy con tăng dần bậc K của dãy số AN là một dãy các số gồm K phần tử trong dãy đó thỏa mãn tính chất tăng dần. Bài toán được đặt ra là hãy tìm số các dãy con tăng dần bậc K của dãy số AN.

 

Input: Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test được xây dựng theo khuôn dạng sau:

  • Dòng đầu tiên ghi lại hai số N và K tương ứng với số phần tử của dãy số và bậc của dãy con.
  • Dòng kế tiếp ghi lại N số của dãy số AN, các số trong dãy không lớn hơn 100. 

 

Output: Với mỗi bộ test, in ra màn hình số các dãy con tăng dần tự nhiên bậc K của dãy số AN. 

Example

Input:

2
5 3
2 5 15 10 20  
5 3
2 20 10 15 5

Output:

7
1

ID RESULT TIME
code...


Submit solution!
Được gửi lên bởi:adm
Ngày:2011-10-20
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
Nguồn bài:ACM PTIT 2011
hide comments
2022-06-24 22:06:39
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[105];
ll F[105][105][105];
int n, k;

void solve() {
cin >> n >> k;
int high = INT_MIN;
for(int i = 1; i <= n; i++) {
cin >> a[i];
high = max(high, a[i]);
}
memset(F, 0, sizeof(F));
for(int i = 1; i <= n; i++) F[i][1][a[i]] += 1;
for(int i = 1; i <= n; i++) {
for(int l = 1; l <= i; l++) {
for(int j = 0; j <= high; j++) {
F[i][l][j] += F[i - 1][l][j];
if(j < a[i]) F[i][l][a[i]] += F[i - 1][l - 1][j];
}
}
}
ll res = 0;
for(int j = 0; j <= high; j++) {
res = res + F[n][k][j];
}
cout << res << endl;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int t = 1;
cin >> t;
for(int tc=1; tc<=t; tc++) {
solve();
}
}
2019-07-31 14:59:05
Code Tham Khao: https://ideone.com/IzhqUl
2017-08-21 09:23:59 Ðặng Minh Tiến
https://kienthuc24h.com/bcacm11g-spoj-ptit-day-con-tang-dan-tu-nhien-bac-k/
2017-07-14 10:15:11
BCACM11G: https://e16cn-ptit.blogspot.com/2017/12/bcacm11g-day-con-tang-dan-tu-nhien-bac-k.html

Last edit: 2017-12-08 07:43:43
2015-10-20 18:11:36 -_-
k<=n<=100
time =0.1s
Quay lui cũng AC :3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.