KVIP – spoj

23/12/2016 by Leave a Comment

Đề bài:

Thuật toán:

Giả sử người 1 (VIP) ngồi ở vị trí k1 thì:

– Người 2,3,…,k1-1 sẽ ngồi đúng vị trí của mình: 2,3,…,k1-1

– Người k1 có 2 cách chọn vị trí ngồi:

— Chọn ngồi ở vị trí 1: những người k1+1,k1+2,…,n sẽ ngồi đúng vị trí của mình

— Chọn ngồi ở vị trí k2>k1: người k1+1,k1+2,…,k2-1 sẽ ngồi đúng vị trí

— Người k2 có 2 cách chọn vị trí ngồi:

——– Chọn ngồi ở vị trí 1: những người k1+1,k1+2,…,n sẽ ngồi đúng vị trí của mình

——– Chọn ngồi ở vị trí k3: người k2+1,k2+2,…,k3-1 sẽ ngồi đúng vị trí

……

 

Đề bài quy về chọn 1 dãy các phần tử: k1,k2,k3,…,kx,1 ( với k1<k2<k3…<kx )

Tức là:

– Người 1 ngồi vị trí k1

– Người k1 ngồi vị trí k2

– Người k2 ngồi vị trí k3

…

– Người kx-1 ngồi vị trí kx

– Người kx ngồi vị trí 1

– Những người còn lại ngồi đúng vị trí của mình

 

Kết quả của dãy đã chọn là:

A[1,1] + A[2,2] + … + A[n,n] – A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1]

Đặt S=A[1,1] + A[2,2] + … + A[n,n], S không đổi

=> Cần tìm dãy sao cho:

(- A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1]) đạt giá trị lớn nhất

Gọi F[i] là tổng lớn nhất của dãy {k1,k2,…,i,1} ( người i ngồi vị trí 1 )

  • F[i] = – A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1] ( với kx=i )
  • F[i] = max ( F[i], F[j] – A[j,1] + A[j,j] + A[i,1] – A[i,i] ) với ( i>j )

Kết quả bài toán: S + F (max)

Code:

uses    math;
const   fi      ='';
        fo      ='';
        maxn    =1000;
 
var     a       :Array[1..maxN,1..maxN] of longint;
        f       :Array[1..maxN] of int64;
        n       :longint;
 
procedure Optimize;
var     i , j   :longint;
        ans :int64;
        maxF    :int64;
begin
        f[1]:=0;
        for i:=1 to n do f[1]:=f[1]+a[i,i];
        for i:=2 to n do
                begin
                        f[i]:=low(int64);
                        for j:=i-1 downto 1 do
                                f[i]:=max(f[i],f[j]-a[j,1]+a[j,i]-a[i,i]+a[i,1]);
                end;
        maxF:=f[1];
        for i:=2 to n do maxF:=max(maxF,f[i]);
        writeln(maxF);
end;
 
procedure run;
var     i, j    :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                for j:=1 to n do read(a[i,j]);
        Optimize;
        close(input);close(output);
end;
 
begin
        run;
end.
Chủ đề: Quy hoạch động Mức độ:

DIFFSTR – spoj

23/12/2016 by Leave a Comment

Đề bài:

Thuật toán:

Solution ăn 60%:

Xét xâu S và dãy x[1..n] thỏa mãn 1 <= x[i] <= length(S) và x[i] > x[i – 1]. Với mỗi dãy x, ta thu được 1 xâu con của S: S[x[1]] S[x[2]] S[x[3]]… S[x[n]]

Để tạo ra được các xâu con phân biệt của S mà 2 phần tử liền kề khác nhau, ta chỉ xét đến những dãy x thỏa mãn điều kiện sau:

  1. S[x[i]] != S[x[i – 1]]
  2. Không tồn tại số k thỏa mãn x[i] < k < x[i + 1] và S[k] == S[x[i + 1]] (nói nôm na là nếu chọn ký tự ch nào đó để cho vào xâu con thì luôn chọn ký tự có chỉ số nhỏ nhất)

(cái đoạn in nghiêng này hình như không cần thiết :)))

 Gọi g[i][j] là số cách chọn dãy x[] có i phần tử mà x[i] = j.

 g[i][j] sẽ cập nhật cho g[i + 1][k] mà k là những giá trị mà khi thêm x[i + 1] = k thì vẫn đảm bảo điều kiện của dãy x[] ở trên (nhận xét là sẽ có không quá 26 giá trị của k)

g[i + 1][k] += g[i][j]

Cuối cùng, để tính kết quả bài toán:

Gọi:

  • f[i][j][0] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con bằng với xâu b[1..i]
  • f[i][j][1] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con lớn hơn xâu b

Với mỗi f[i][j][t], tìm các giá trị k thỏa mãn thêm x[i + 1] = k vẫn đảm bảo thỏa mãn điều kiện của x[]:

– Nếu t = 1 thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] = b[i + 1] thì f[i + 1][k][0] += f[i][j]

– Nếu t = 0, S[x[k]] > b[i + 1] thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] < b[i + 1] thì không làm gì hết

Kết quả bài toán = tổng f[i][j][1] + tổng f[length(b)][j][0]

Đpt ít hơn O(n * n * log(n)) n * n là mảng f, log(n) để tìm k, thực chất là không cần tính hết mảng f nên đpt sẽ nhỏ hơn khá nhiều

Solution ăn 100%:

QHĐ tương tự như trên, ta có thể tính được số xâu con của S[i..n] bắt đầu bằng ký tự ch bất kỳ mà thỏa mãn 2 ký tự liền kề khác nhau trong O(1)

Duyệt i từ đầu đến cuối xâu b, đến bước thứ i, đếm số xâu con trong S có dạng b[1..i – 1] + x với x là 1 xâu < S[i..m]. Số lượng xâu x = (số xâu con trong S[k..n] (k là vị trí kết thúc đầu tiên của xâu con b[1..i – 1] trong xâu S) bắt đầu bằng các ký tự < b[i]) + 1 (xâu rỗng)

Kết quả bài toán là tổng của các xâu trên – 1 (xâu rỗng)

Lưu ý là trong khi duyệt, nếu xâu b[1..i] không thỏa mãn điều kiện  2 ký tự liền kề khác nhau thì phải dừng duyệt ngay lập tức.

Solution O(N): của anh Nguyễn Tấn Sỹ Nguyên ( flash_mt )

Gọi F[i] là số cách chọn 1 subsequence ko có 2 phần tử kề nhau bằng nhau với S[i] là phần tử đầu tiên. Có thể tính F[] trong O(26N).

Sau đó ta đếm số lượng subsequence A thỏa A[1..k] = B[1..k] và A[k + 1] > B[k + 1]. Với mỗi giá trị k, xét A[k + 1] = c với c > B[k + 1], tìm vị trí u đầu tiên trong đoạn còn lại thỏa S[u] = c và tăng kết quả lên f[u]. Độ phức tạp của bước này là O(26(M + N)).

Code:

  • (đang cập nhập)
Chủ đề: Quy hoạch động Mức độ:

NKPANO – spoj

23/12/2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Sắp xếp các công nhân tăng dần theo S
  • Gọi F[i] là tổng tiền công lớn nhất nếu sơn đến vạch i.
    Với mỗi công nhân thứ k: F[i]=max(F[i],F[j-1]+(i-j+1)*P[k]), trong đó: S[k]<=i<=S[k]+L[k]-1, i-L[k]+1<=j<=S[k]

Code:

#include <bits/stdc++.h>
#define maxn 16010
using namespace std;
int n,k,l;
int f[maxn+1],maxf[maxn+1],maxr[maxn+1];
struct  te{
    int l,p,s;
};
te a[102];
template <typename T> inline void read(T &x){
	x = 0; char c;
	while (!isdigit(c = getchar())) {}
	do x = x * 10 + c - '0'; while (isdigit(c = getchar()));
}
template <typename T> inline void write(T x){
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
void    docdl(){
    read(n); read(k);
    for(int i=1;i<=k;i++){
        read(a[i].l);
        read(a[i].p);
        read(a[i].s);
    }
}
bool    cmp(te a,te b){
    return (a.s<=b.s);
}
void    xuli(){
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++){
        maxr[a[i].s+1]=-1000000000;
        for(int j=a[i].s;j>=max(a[i].s-a[i].l+1,1);j--) maxr[j]=max(maxr[j+1],maxf[j-1]-(int)j*a[i].p);
        for(int j=a[i].s;j<=min(a[i].s+a[i].l-1,n);j++){
            f[j]=max(f[j],maxr[max(j-a[i].l+1,1)]+(int)(j+1)*a[i].p);
            maxf[j]=max(f[j],maxf[j-1]);
        }
        for(int j=1;j<=n;j++) maxf[j]=max(maxf[j],maxf[j-1]);
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    write(res);
}
int     main(){
    docdl();
    xuli();
}
Chủ đề: Quy hoạch động Mức độ:

DTDOI – spoj

05/12/2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Thông thường thì ta sẽ có cách giải QHĐ với đpt O(S*n), nhưng vì S lên đến 1e9 nên ta có cách làm như sau:
    • Giảm S bằng tờ có giá trị lớn nhất cho đến khi S đủ nhỏ để QHĐ (giảm đến mức nào thì các bạn nên tự thử, trong code mình giảm xuống 100000)
    • QHĐ

Code:

#include<bits/stdc++.h>
using namespace std;
int n,s;
int a[101];
int d[100001];
int main()
{
	cin>>n>>s;
	for (int i=1; i <= n; i++)
		cin>>a[i];
	int mx=0;
        for (int i=1; i <= n; i++)
                mx=max(mx,a[i]);
	int res=0;
	while (s >= 100001)
		{
			res++;
			s-=mx;
		}
	d[0]=0;
	for (int i=1; i <= s; i++)
		{
                        d[i]=10000000;
                        for (int j=1; j <= n; j++)
			        if (i >= a[j])
				         d[i]=min(d[i],d[i-a[j]]+1);
                }
	cout<<res+d[s];
	return 0;
}
Chủ đề: Quy hoạch động Mức độ:

LCS2X – spoj

02/12/2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Gọi L[i,j] là độ dài dãy con chung bội hai dài nhất với số cuối cùng là A[i] và B[j]1) Với A[i] <> B[j] thì L[i,j] = 0

    2) Với A[i] = B[j] thì L[i,j] = max(L[x,y] + 1) ( với x<i, y<j, A[x]*2 <= A[i] )

  • Để tính max(L[x,y]) nhanh chóng, ta sử dụng mảng F với ý nghĩa:F[y] = max(L[x,y])   =>Kết quả là max(F[j]) (với 1<=j<=n)

    Gọi ma=max(F[y]) ( với y<j, B[y]*2 <= A[i] )

    Khi đó ta có đoạn code phần xử lý sẽ là:

    for (i=1;i<=m;++i){
        ma=0;
        for (j=1;j<=n;++j){
            matruocj=ma;
            if (b[j]*2<=a[i]) ma=max(ma,f[j]);
            if (a[i]==b[j]) f[j]=max(f[j],matruocj+1);
        }
    }
  • Với cách này thì bạn chỉ cần dùng mảng 1 chiềuĐộ phức tạp: O(M*N)

Code:

uses    math;
const   fi      ='';
        fo      ='';
        oo      =trunc(1e4);
 
var     a, b, f :array[0..oo] of longint;
        ma,matruocj     :longint;
        ans     :longint;
        m, n    :longint;
procedure Optimize;
var     i, j    :longint;
begin
        fillchar(f, sizeof(f),0);
        for i:=1 to m do
                begin
                        ma:=0;
                        for j:=1 to n do
                                begin
                                        matruocj:=ma;
                                        if b[j]*2<=a[i] then ma:=Max(ma,f[j]);
                                        if b[j]=a[i] then f[j]:=max(f[j],matruocj+1);
                                end;
                 end;
 
end;
 
Procedure run;
var     i, t,l :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(t);
        for l:=1 to t do
                begin
                        readln(m, n);
                        for i:=1 to m do read(a[i]);
                        for i:=1 to n do read(b[i]);
                        Optimize;
                        ans:=0;
                        for i:=1 to n do
                                if f[i]>ans then ans:=f[i];
                        writeln(ans);
                end;
        close(input);close(output);
end;
 
begin
        run;
end.
Chủ đề: Quy hoạch động, SPOJ Mức độ:

NKJUMP – spoj

30/10/2016 by Leave a Comment

Đề bài: [xem đề bài]

Thuật toán:

  • Nhận thấy một vòng bất kỳ chỉ có thể nhảy đến vòng có số lớn hơn. Ta nghĩ đến sử dụng phương pháp Quy hoạch động để giải.
  • Ban đầu sắp xếp lại mảng A.
  • Gọi F[i] là số bước lớn nhất để nhảy đến ô thứ i.
  • F[i] = max(F[j]+1, F[i]) với i=1..n, j=1..i-1 và tồn tại k sao cho a[k]+a[j]=a[i].
  • Kiểm tra xem có tồn tại k bằng cách sử dụng tìm kiếm nhị phân

Code:

C++ (xem code trên ideone)

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 1009;
int i, j, n, a[maxn], b[maxn], f[maxn];
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    int tmp, ans = 0;
    for (int i = 1; i <= n; i++) f[i] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            bool tmp = binary_search(a+1,a+j,a[i] - a[j]);
            if (tmp == 1) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

Pascal (xem code trên ideone)

uses    math;
const   fi='';
        fo='';
        maxn=1000;
type    arra=array[1..maxn] of longint;
var     f:text;
        a,l:arra;
        i,j,n:integer;
        tmp2:longint;
        res:longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do
    begin
        read(f,a[i]);
    end;
    close(f);
end;
procedure sort;
var     w:longint;
begin
    for i:=1 to n do
        for j:=i+1 to n do
        if a[i]>a[j] then
        begin
            w:=a[i];
            a[i]:=a[j];
            a[j]:=w;
        end;
end;
procedure init;
begin
    res:=0;
    for i:=1 to n do l[i]:=1;
end;
function kt(x,k:longint):boolean;
var     d,c,g,ii:longint;
begin
    d:=1; c:=k;
    kt:=false;
    while d<=c do
    begin
        g:=(d+c) div 2;
        if a[g]=x then begin tmp2:=g; exit(true); end;
        if a[g]<x then d:=g+1 else c:=g-1;
    end;
end;
function max3(x,y,z:longint):longint;
begin
    max3:=x;
    if y>max3 then max3:=y;
    if z>max3 then max3:=z;
end;
procedure xuly;
var     tmp:longint;
begin
    for i:=1 to n do
    begin
        tmp:=a[i];
        for j:=i-1 downto 1 do
        begin
            if a[j]>=tmp div 2 then
                begin
                   if kt(tmp-a[j],j-1) then
                        begin
                        l[i]:=max3(l[i],l[j]+1,l[tmp2]+1);
                        if l[i]>res then res:=l[i];
                        end;
                end
            else break;
        end;
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    sort;
    init;
    xuly;
    xuat;
end.
Chủ đề: Quy hoạch động, Tìm kiếm nhị phân Mức độ:

SEQ198 – spoj

09/10/2016 by 9 Comments

Đề bài:

Thuật toán:

  • Sử dụng phương pháp quy hoạch động kết hợp với bitmask.
  • Sắp xếp lại mảng A.
  • f[i,state] là số phần tử cần loại bỏ của dãy A[1..i] khi có state là trạng thái giữ hoặc chọn của 10 số cuỗi của dãy.

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; ++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 X first
#define Y second
#define ll long long
#define mp make_pair
#define pb push_back
#define endl '\n'
 
const int MAXN = 1e5 * 5;
const int inf = 1024;
const int N = 5000;
 
using namespace std;
int n,p[N],a[N],b[N],l[N],ans,ss,c[N],f[2001][1025];
 
void update()
{
    int cnt = 0;
    int dem = 0;
    FORE(i,1,min(n,10))
    if (l[i])
            c[++cnt] = a[i],dem += b[i];
    sort(c+1,c+cnt+1);
    FORE(i,1,cnt)
    FORD(j,i-1,1)
    if (c[i] - c[j] > 9) break;
    else
    {
        if (c[i] - c[j] == 1) return;
        if (c[i] - c[j] == 8) return;
        if (c[i] - c[j] == 9) return;
    }
    f[10][ss] = dem;
    ans = max(ans , dem);
}
 
void duyet(int i)
{
    FORE(j,0,1)
    {
        ss = ss*2 + j;
        l[i] = j;
        if (i == min(n,10)) update();
        else duyet(i+1);
        ss /= 2;
    }
}
 
int ok(int u,int v)
{
    if (u - v == 1) return 1;
    if (u - v == 8) return 1;
    if (u - v == 9) return 1;
    return 0;
}
 
int check(int s,int i)
{
    FORE(j,0,8)
    {
        int xx = (s >> j)&1;
        if (xx && ok(a[i],a[i - j - 1])) return 1;
    }
    return 0;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("", "r", stdin);
    freopen("", "w", stdout);
    #endif //yeulaptrinh.pw
    cin>>n;
    int lx = n;
    FORE(i,1,n) cin>>p[i];
    sort(p+1,p+n+1);
    int po = -1;
    int n1 = 0;
    FORE(i,1,n)
    if (p[i] != po)
    {
        po = p[i];
        ++n1;
        a[n1] = p[i];
        ++b[n1];
    }
    else ++b[n1];
    n = n1;
    duyet(1);
    if (n <= 10)
    {
        cout<<lx - ans;
        return 0;
    }
    FORE(i,10,n-1)
    FORE(x,0,1023)
    {
        int xx = (2*x)%inf;
        f[i+1][xx] = max(f[i+1][xx] , f[i][x]);
        if (check(x,i+1)) continue;
        xx = (2*x + 1)%inf;
        f[i+1][xx] = max(f[i+1][xx] , f[i][x] + b[i+1]);
    }
    int kq = 0;
    FORE(i,10,n)
    FORE(x,0,1024)
        kq = max(kq , f[i][x]);
    cout<<lx - kq;
    return 0;
}
uses math;
const
  fi = '';
var
  a,b,cnt : array[0..2001] of longint;
  f : array[0..2001,0..511] of longint;
  dd : array[0..2001,0..511] of boolean;
  n,n1 : longint;
 
procedure enter;
  var
    i : longint;
  begin
    assign(input,fi);
    reset(input);
    readln(n);
    for i := 1 to n do
      read(b[i]);
    close(input);
  end;
 
 
procedure qsort(l,r : longint);
  var
    i,j,k,tmp : longint;
  begin
    i := l;
    j := r;
    k := b[l + random(r - l + 1)];
    while i < j do
      begin
        while b[i] < k do inc(i);
        while b[j] > k do dec(j);
        if i <= j then
          begin
            tmp := b[i];
            b[i] := b[j];
            b[j] := tmp;
            inc(i);
            dec(j);
          end;
      end;
    if l < j then qsort(l,j);
    if i < r then qsort(i,r);
  end;
 
function getbit(x,i : longint) : longint;
  begin
   exit(1 and (x shr (i - 1)));
  end;
 
function check(stt : longint) : boolean;
  begin
    if (getbit(stt,1) = 1) or (getbit(stt,8) = 1) or (getbit(stt,9) = 1) then exit(false);
    exit(true);
  end;
 
function batbit(x,i : longint) : longint;
  begin
    exit(x or (1 shl (i - 1)));
  end;
 
function sttnext(tt,stt,i : longint) : longint;
  var
    res,kc,j : longint;
  begin
    kc := a[i+1] - a[i];
    res := 0;
    for j := 0 to 9 - kc do
      if j = 0 then
        begin
          if tt = 1 then res := batbit(res,kc)
        end
      else
        if getbit(stt,j) = 1 then
          res := batbit(res,kc + j);
    exit(res);
  end;
 
procedure init;
  var
    i,j : longint;
  begin
    qsort(1,n);
    a[1] := b[1];
    j := 1;
    cnt[1]:=1;
    for i := 2 to n do
      if b[i] <> a[j] then
        begin
          inc(j);
          a[j] := b[i];
          cnt[j] := 1;
        end
      else inc(cnt[j]);
    n1:=j;
    a[n1+1] := high(longint)
  end;
 
function cal(i,stt: longint) : longint;
  var
    ff : longint;
  begin
    if dd[i,stt] then exit(f[i,stt]);
    dd[i,stt] := true;
    if i = n1 + 1 then
      ff := 0
    else
      begin
        ff := cal(i + 1,sttnext(0,stt,i)) + cnt[i];
        if check(stt) then
          ff := min(ff,cal(i + 1,sttnext(1,stt,i)));
      end;
    f[i,stt] := ff;
    exit(ff);
  end;
 
procedure print;
  begin
    writeln(cal(1,0));
  end;
 
begin
  enter;
  init;
  print;
end.
Chủ đề: Bitmask, Quy hoạch động Mức độ: ,