NDCCARD – spoj

Đề bài:

• http://vn.spoj.com/problems/NDCCARD/

Thuật toán:

• Dùng mảng f[i] đánh dấu giá trị lớn nhất <= i trong dãy A.
• Vậy nên các cặp 3 số là a[i], a[j], f[m-a[i]-a[j]].
• Chú ý đề bài cho dãy A đôi một khác nhau nhé.

Code:

• C++ (xem)

#include 

using namespace std;

const int oo = 500001;
const int MAXN = 10001;
int i, j, n, m, a[MAXN], tmp, res, f[oo];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    tmp = 0;
    for (int i = a[1]; i <= m; i++) {
        if ((tmp < n) && (i >= a[tmp+1])) tmp++;
        f[i] = a[tmp];
    }
    for (int i = 1; i<= n-2; i++) {
        for (int j = i+1; j <= n-1; j++) {
            tmp = m - a[i] - a[j];
            if (tmp < 1) continue;
            tmp = f[tmp];
            if (tmp <= a[j]) continue;
            res = max(res, a[i] + a[j] + tmp);
        }
    }
    cout << res;
    return 0;
}

• Pascal (xem)

CONST fin='';
     fout='';
VAR res, i, j, n, m, x, min: longint;
    a, ok: array[1..1000000] of longint;
    f: text;
BEGIN
  Assign(f,fin);
  Reset(f);
  Readln(f,n,m);
  min:=maxlongint-1;
  For i:=1 to n do
    Begin
      Read(f,a[i]);
      ok[a[i]]:=a[i];
      If a[i]0 then
          Begin
            If (ok[x]<>a[i]) and (ok[x]<>a[j]) and (ok[i]<>0) then
              If a[i]+a[j]+ok[x]>res then res:=a[i]+a[j]+ok[x];
          End;
      End;
  Assign(f,fout);
  Rewrite(f);
  Writeln(f,res);
  Close(f);
END.