Ngày 11-1-2019 - Bài 1

CHNREST - Chinese restaurant

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: nguyenxuanhaa3

Hàng năm vì muốn có không khí ấm cúng và cũng để tiết kiệm nên bạn thường tổ chức sinh nhật ở nhà. Tuy nhiên trước sinh nhật năm nay vài hôm bạn đã thi đậu vào đội tuyển tin học quốc gia. Đây là một sự kiện đặc biệt có ý nghĩa nên bạn quyết định mừng ngày sinh nhật của mình tại một nhà hàng Trung Quốc sang trọng và bạn tự nhủ lần này nhất định phải tiêu xài rộng tay hơn. Mọi việc chuẩn bị đã gần xong nhưng còn một vấn đề làm bạn khá nhức đầu, đó là làm sao chọn được những món ăn mà mọi người cùng thích. Nhà hàng có M món ăn khác nhau và thú vị ở chỗ là mỗi món ăn rất nhiều nên có thể đủ cho bao nhiêu người cũng được, vì thế vấn đề là gọi món nào chứ không phải mỗi món gọi bao nhiêu.

Có tất cả N người đến dự tiệc sinh nhật (bao gồm cả bạn trong đó). Bạn đã tìm hiểu được danh sách những món ăn yêu thích của từng người và bạn muốn rằng đối với mỗi người phải có ít nhất 2 món mà họ thích. Tuy nhiên sau khi ăn xong còn nhiều tiết mục hấp dẫn khác nên bạn cũng muốn rằng bất kỳ ai cũng không có quá 2 món ăn yêu thích trong danh sách được đặt trước. Và vấn đề cuối cùng, đây là tiền của bố mẹ nên cũng không nên tiêu xài quá đáng.

Yêu cầu

Hãy cho biết số tiền ít nhất phải trả để gọi một thực đơn thỏa mãn các yêu cầu trên.

Dữ liệu

- Dòng đầu tiên chứa hai số M, N

- Dòng thứ hai chứa M số Pi là giá của món thứ i.

- Trong N dòng cuối cùng, dòng thứ k ghi danh sách các món yêu thích của người thứ k.

Kết quả

- Gồm một số duy nhất là kết quả của bài toán, hoặc

- in ra -1 nếu không có cách gọi món nào thỏa mãn. 

Nguồn bài : http://vn.spoj.com/problems/CHNREST/

Ví dụ

• input
  5 3
  100 150 300 425 200
  1 2 4
  1 3 4 5
  1 4 5
  output
  450

Lời giải:

#include <bits/stdc++.h>
using namespace std;
long long on[100000];
bool b[100][1000];
long long m, n;
long long p[1000000];
long long F[33][60000];
long long go(long long pos, long long state)
{
 if(pos == m)
    {
  if(state == on[n] - 1) return 0;
  else return 1000000000;
 }
 if(F[pos][state] != -1)
 return F[pos][state];
 long long res = go(pos + 1, state);
 bool ok = true;
 for(long long i=0;i<n;++i)
    if(b[pos][i] && state / on[i] % 3 == 2)
    {
        ok = false;
        break;
    }
 if(ok)
 {
  long long ns = state;
  for(long long i=0;i<n;++i)
   if(b[pos][i])
    ns += on[i];
  res = min( res, p[pos] + go( pos + 1, ns));
 }
 return F[pos][state] = res;
}
main()
{
 cin >> m >> n;
 for(long long i=0;i<m;++i) cin >> p[i];
 string s;
 getline( cin, s);
 for(long long i=0;i<n;++i) {
  getline( cin, s);
  istringstream iss(s);
  long long x;
  while(iss >> x) {
   b[x-1][i] = true;
  }
 }
  on[0] = 1;
  for(long long i=1;i<11;++i)
   on[i] = 3 * on[i - 1];
  memset(F,-1, sizeof(F));
  long long best = go( 0, 0);
  if(best < 1000000000)
   cout << best << endl;
  else
   cout << -1 << endl;
}