Tin học Chuyên đề quy hoạch động

L

lamdetien36

Em góp 1 bài cho box Tin đỡ vắng :)>-
Đề bài:
Cho n phần tử khác nhau, hỏi có bao nhiêu cách chia n phần tử đó thành k nhóm mà mỗi nhóm có ít nhất 1 phần tử (các hoán vị của các nhóm được xem là 1 cách).

Dữ liệu vào :
Dòng đầu tiên chứa số T là số test.
T dòng tiếp theo mỗi dòng chứa 2 số N và K, với 1<=K<=N<=25
Dữ liệu ra :
T dòng, mỗi dòng là số cách với test tương ứng.

Input:
1
4 2
Output:
7
Giải thích: 7 cách chia đó là (ABC)(D) , (ABD)(C) , (ADC)(B) , (DBC)(A) , (AB)(CD) , (AC)(BD) , (BC)(AD).

Hướng dẫn giải:
Gọi F[i, j] là số cách chia i phần tử vào j nhóm.
Kết quả bài toán sẽ là F[N, K].

Cơ sở QHĐ:
Mã: 
F[i, 1] = 1
F[i, i] = 1
Hai điều trên là hiển nhiên
Công thức truy hồi:
Mã: 
F[i, j] = F[i - 1, j - 1] + j * F[i - 1, j]
Giải thích CTTH:
Tính F[i, j].
Giả sử đã chia được i - 1 phần tử vào j nhóm, như thế ta chỉ cần thêm 1 phần tử nữa vào một trong những nhóm đã chia thì ta được kết quả. Phần tử cần thêm có thể được thêm vào 1 trong j nhóm đã có. Như vậy công thức sẽ là j * F[i - 1, j].
Giả sử đã chia được i - 1 phần tử vào j - 1 nhóm, như thế ta chỉ cần thêm 1 phần tử nữa vào 1 nhóm mới. Tức là công thức là F[i - 1, j - 1]
Vậy CTTH là F[i - 1, j - 1] + j * F[i - 1, j]
Bấm để xem đầy đủ nội dung ...
Độ phức tạp: O(N * K)
 
T

thienvamai

unsigned long long là số 64bit ko dấu
còn long long là 64 bit có dấu
mình để long long đc 90 điểm ->code số lớn :))
 
L

lamdetien36

Một bài khác mà cách làm em cho là khá giống QHĐ :D
Đề bài:
Cho 1 dãy ngoặc độ dài N (N <= 10^6). Tìm độ dài dãy ngoặc con đúng dài nhất của dãy ngoặc đã cho.
Test VD:
Input:
Mã: 
)((())))(()())
Output:
Mã: 
6
Hướng dẫn:
Gọi:
- D là vị trí dấu mở ngoặc tương ứng với vị trí i (nếu st là dấu đóng ngoặc).
- C là vị trí dấu mở ngoặc đầu tiên thỏa mãn st[C --> i] là dãy ngoặc đúng.
Khi đó kết quả chỉ đơn giản là
Mã: 
Max(i - C[i]) với 0 <= i < N và st[i] == ')'
Cơ sở QHĐ: đếu có :p
Công thức truy hồi:
Ta sử dụng 1 stack để làm bài này:

  • Duyệt từng ký tự st của dãy.
    [*]Nếu st == '(' thì đẩy i vào Stack.
    [*]Nếu st == ')' thì có 2 trường hợp xảy ra:


  1. Nếu stack rỗng thì chứng tỏ không tồn tại dấu mở ngoặc tương ứng với st, nên C = D = -1.
    [*]Nếu stack không rỗng, hiển nhiên vị trí trong đỉnh stack chính là vị trí dấu mở ngoặc tương ứng với st, nên D = đỉnh stack. Để tính C, ta kiểm tra xem st[D - 1] có phải là dấu đóng ngoặc không và C[D - 1] có khác -1 không. Nếu có, C = C[D - 1], ngược lại C = D

Giải thích:
Nếu st[D - 1] là dấu đóng ngoặc và C[D - 1] != -1 thì dãy st[C[D - 1] --> D - 1] sẽ là 1 dãy ngoặc đúng. Nối dãy trên với dãy st[D - 1 --> i] vừa tìm được thì ta hiển nhiên có được dãy ngoặc đúng dài hơn.
Độ phức tạp: O(N)
Code minh họa:
PHP: 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <utility>
#include <algorithm>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cctype>
#include <cmath>

using namespace std;

typedef long long longs;

int main() {
    string st;
    int N, i;

    cin >> st;
    N = st.length();

    int C[1000000], D[1000000];
    stack<int> S;
    for (i = 0; i < N; ++i) {
        if (st[i] == '(') {
            S.push(i);
        }
        else {
            if (S.empty())
                C[i] = D[i] = -1;
            else {
                D[i] = S.top();
                S.pop();
                if (st[D[i] - 1] == ')' && C[D[i] - 1] != -1)
                    C[i] = C[D[i] - 1];
                else
                    C[i] = D[i];
            }
        }
    }
    for (i = 0; i < N; ++i)
        C[i] = i - C[i];

    int res = 0
    for (i = 0; i < N; ++i) {
        if (D[i] != -1 && st[i] == ')') res = max(res, C[i]);
    }
    if (res == 0)
        cout << 0;
    else
        cout << res + 1;
    return 0;
}

 
Last edited by a moderator:
T

thienvamai

mình nghĩ làm thế này hợp lý hơn:
F là dãy ngoặc đúng dài nhất kết thúc tại i. nếu từ i->j là dãy ngoặc đúng
F[j]=F[i-1]+(j-i+1);
PHP: 
#include <bits/stdc++.h>
#define elif else if
using namespace std;
const int Maxn=1e6+10;
stack<int> ms;
char S[Maxn];
int F[Maxn];
main(){
    ios_base::sync_with_stdio(false);
    cin>>(S+1);
    int n=strlen(S+1);
    for(int i=1;S[i];i++){
        if(S[i]=='(') ms.push(i);
        elif(!ms.empty())  F[i]=F[ms.top()-1]+(i-ms.top()+1),ms.pop();
    }
    cout<<*max_element(F+1,F+n+1);
}
 
V

vansonqtqb

nhờ bạn giải thich rõ hộ minh đoạn code tìm dãy con tăng dài nhất
procedure quyhoachdong;BeginL[1]:=1;T[1]:=0;a[N+1]:=32767;
for i:=2 to N+1 do
begin jmax:=0; L:=1;
for j:=1 to i-1 do
if (a[j]<=a)and (L< L[j]+1) then begin
L:=L[j]+1;
jmax:=j;
end;
T:=jmax;
end;End
;Procedure Truyvet(m:integer);Begin
m:=T[m];
if m=0 then exit;truyvet(m);write(g,a[m],' ');end;
cho mình hỏi l[j] ban dầu và sau mỗi làn lặp giá trị của nó là bao nhiêu
cách truy vet tìm nghiệm mình ko hiểu
mong bạn giup dỡ
giải tich rõ cach tinh bảng pá va cách truy vet
thank
 
T

thuynga07102001@gmail.com

Học sinh mới
Thành viên
27 Tháng tám 2017
3
2
6
11thanhkhoeo said:
Quy hoạch động là một phương pháp rất hiệu quả để giải các bài toán tối ưu tổ hợp. ý tưởng cơ bản của phương pháp này là: để có lời giải của bài toán tối ưu kích thước n, ta giải các bài toán tương tự có kích thước nhỏ hơn và phối hợp lời giải của chúng để được lời giải của bài toán ban đầu. Đó chính là tư tưởng chia để trị một cách rất nghiêm ngặt.
Không phải bài toán nào cũng có thể giải bằng quy hoạch động. Để giải được bằng quy hoạch động, bài toán thoả mãn nguyên lý tối ưu Bellman: mọi dãy con của một dãy tối ưu cũng phải là dãy tối ưu.
Thông thường hàm mục tiêu của bài toán được xây dựng từ một hàm có dạng: f(n) = max(f(k)+g(n)), trong đó k là một số giá trị phù hợp nhỏ hơn n.
Hàm f(n) được gọi là hàm quy hoạch động. Việc tính giá trị hàm f được hiện từ dưới lên, tức là các giá trị n nhỏ được tính trước. Tất cả các kết quả được lưu vào bảng để phục vụ cho việc tính hàm quy hoạch động với các giá trị n lớn hơn.
Chúng ta sẽ xem xét một số bài toán quy hoạch động tiêu biểu để minh hoạ cho các tư tưởng trên.
Bấm để xem đầy đủ nội dung ...
Cao nhân cho em xin fb được không ạ, tại em thấy khá khó hiểu nên muốn tham khảo cao nhân từng tí một theo kiểu mưa dầm thấm lâu ấy ạ!!
 
You must log in or register to reply here.
Top Bottom