SPOJ.com - Problem MIXUP2

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.|

MIXUP2 - Đàn bò hỗn loạn

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mixup2

Mỗi trong N cô bò (4 <= N <= 16) của bác John có một số seri phân biệt S_i (1 <= S_i <= 25,000). Các cô bò tự hào đến nỗi mỗi cô đều đeo một chiếc vòng vàng có khắc số seri của mình trên cổ theo kiểu các băng đảng giang hồ.

Các cô bò giang hồ này thích nổi loạn nên đứng xếp hàng chờ vắt sữa theo một thứ tự gọi được gọi là 'hỗn loạn'.

Một thứ tự bò là 'hỗn loạn' nếu trong dãy số seri tạo bởi hàng bò, hai số liên tiếp khác biệt nhau nhiều hơn K (1 <= K <= 3400). Ví dụ, nếu N = 6 và K = 1 thì 1, 3, 5, 2, 6, 4 là một thứ tự 'hỗn loạn' nhưng 1, 3, 6, 5, 2, 4 thì không (vì hai số liên tiếp 5 và 6 chỉ chênh lệch 1).

Hỏi có bao nhiêu cách khác nhau để N cô bò sắp thành thứ tự 'hỗn loạn'?

Dữ liệu

* Dòng 1: Hai số N và K cách nhau bởi khoảng trắng.

* Dòng 2..N+1: Dòng i+1 chứa một số nguyên duy nhất là số seri của cô bò thứ i: S_i

Kết quả

* Dòng 1: Một số nguyên duy nhất là số cách để N cô bò sắp thành thứ tự 'hỗn loạn'. Kết quả đảm bảo nằm trong phạm vi kiểu số nguyên 64-bit.

Ví dụ

Dữ liệu:
4 1
3
4
2
1

Kết quả:
2

Submit solution!

Được gửi lên bởi:	Phong
Ngày:	2008-11-11
Thời gian chạy:	0.200s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Ngôn ngữ cho phép:	Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:	USACO November 2008

hide comments

2021-07-30 10:47:10
NGUYEN XUAN HIEU HAI PHONG 1 dam AC
ez game ez life
HAI PHONG vo doi

2019-10-24 05:08:40
bài này rất dễ. quay lui là full test. quy hoạch động trạng thái là thứ rất lạc hậu, không nên dùng. quay lui là thuộc về vận trù học nên nó chạy tối ưu hơn quy hoạch động trạng thái.

#include <iostream>
#include <vector>
#include <functional>
using ll = long long;
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
freopen("mixup2.inp", "r", stdin);
#endif
ll n, k;
cin >> n >> k;
vector<ll> A(n);
for (auto &x : A)
cin >> x;
vector<vector<ll>> M(1 << n, vector<ll>(n, -1));
function<ll(ll, ll)>
bt = [&](ll state, ll index) {
if (state == (1 << n) - 1)
return 1LL;
if (M[state][index] != -1)
return M[state][index];
ll sum = 0;
for (ll i = 0; i < n; i++)
if (!(state & (1 << i)) && abs(A[index] - A[i]) > k)
sum += bt(state | (1 << i), i);
return M[state][index] = sum;
};
ll count = 0;
for (ll i = 0; i < n; i++)
count += bt(1 << i, i);
cout << count;
}

Last edit: 2019-10-24 05:29:47

2019-09-27 05:25:52
1 dam :)
duonght_pro_xinhgainhathemattroi_:)

2019-08-11 18:48:29
bài này thì xài Kruskal + HLD là AC

2018-09-25 10:50:40
Tớ là Sơn hello cân tất cả

2018-01-06 08:41:11
80đ bị sao vậy nhỉ? cao nhân nào chỉ với!!

2017-09-18 09:53:23
trau cung AC

2017-09-18 09:47:43
ez. bai nay dung nhan ma tran vs heap la ac

2017-09-18 09:45:48
quá ez
ai o biết thì tham khảo code của mình nhé !!!! :))))))))))))))))))))))

2017-09-18 09:45:01
Một bài quy hoạch động trạng thái cơ bản

Gọi dp[mask][i] là số lượng cách sắp xếp trạng thái mask hỗn loạn và có con bò cuối cùng là i
Quy ước mask như sau: ở vị trí i là bit 1 là trong dãy có bò i, ngược lại nếu là bit 0 là ko có bò i

Vậy dp[mask][i] sẽ bằng các tổng các dp[new_mask][j] với new_mask = mask ^ (1 << i) tức là dãy ko có bò i, và chênh lệch bò i và bò j phải quá k (abs (s[i] - s[j]) > k)

Kết quả bài toán sẽ là tổng các dp[(1 << n) - 1][i] (với i = 0 -> n-1)

Giải bài trực tuyến

MIXUP2 - Đàn bò hỗn loạn

Dữ liệu

Kết quả

Ví dụ