Domino
Xem dạng PDF
Nhân dịp tết, Bananabread đã về quê ăn tết cùng với họ hàng của mình. Các anh em họ của Bananabread đã tạo ra một trò chơi để đố anh ấy.
Cho một bảng ~N \times M~, ô ở dòng thứ ~i~ và cột thứ ~j~ có giá trị là ~A_{i,j}~. Các anh em họ của Bananabread đã đưa cho anh ~k~ miếng domino ~2 \times 1~ để đặt lên bảng. Các miếng domino có thể xoay ngang hoặc dọc, tuy nhiên phải đặt sao cho không đè lên nhau. Họ đố Bananabread hãy đặt sao cho các ô được phủ bởi domino có tổng lớn nhất có thể.
Yêu cầu: Hãy giúp Bananabread xem là tổng lớn nhất đạt được có thể là bao nhiêu.
Input
Dòng đầu gồm ~3~ số nguyên là ~N,M,K~. ~(1\le N\le 4,1\le M\le 1000,1\le K \le \frac{N*M}{2})~
~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số nguyên. ~(|A_{i,j}| \le 10^9)~
Output
Gồm ~1~ số nguyên là tổng lớn nhất đạt được
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~M\le5~ |
| 2 | ~40~ | ~N\le3~ |
| 3 | ~40~ | Không có ràng buộc gì thêm |
Sample Input 1
3 5 4
5 6 -9 -3 8
8 4 5 -10 -2
1 0 -10 9 -1
Sample Output 1
37
Notes
Cách đặt tối ưu cho ví dụ trên:
Bình luận
include <bits/stdc++.h>
using namespace std; typedef long long ll; const ll NEG = -1000000000000000000LL;
int N, M, K; vector g;
struct Transition { int nxt, cnt; vector<int> vert, horiz; };
void dfsTrans(int pos, int cur, int nxt, int cnt, vector<int>& v, vector<int>& h, bool horizAllowed, int N, vector<Transition>& res) { if(pos == N) { res.pushback({nxt, cnt, v, h}); return; } if(cur & (1<<pos)) { dfsTrans(pos+1, cur, nxt, cnt, v, h, horizAllowed, N, res); return; } dfsTrans(pos+1, cur | (1<<pos), nxt, cnt, v, h, horizAllowed, N, res); if(pos+1 < N && !(cur & (1<<(pos+1)))) { v.pushback(pos); dfsTrans(pos+2, cur | (1<<pos) | (1<<(pos+1)), nxt, cnt+1, v, h, horizAllowed, N, res); v.popback(); } if(horizAllowed && ((nxt & (1<<pos))==0)) { h.pushback(pos); dfsTrans(pos+1, cur | (1<<pos), nxt | (1<<pos), cnt+1, v, h, horizAllowed, N, res); h.pop_back(); } } vector<Transition> transArr[2][16];
int main(){ ios::syncwithstdio(false); cin.tie(nullptr); cin >> N >> M >> K; g.assign(N, vector<ll>(M)); for(int i=0;i<N;i++) for(int j=0;j<M;j++) cin >> g[i][j]; int states = 1<<N; for(int mask=0; mask<states; mask++){ for(int flag=0; flag<2; flag++){ vector<Transition> res; vector<int> v, h; dfsTrans(0, mask, 0, 0, v, h, flag==1, N, res); transArr[flag][mask] = res; } } vector cur(states, vector<ll>(K+1, NEG)), nxtDP(states, vector<ll>(K+1, NEG));
cur[0][0] = 0;
for(int col=0; col<M; col++){
bool horizAllowed = (col < M-1);
int flag = horizAllowed ? 1 : 0;
for(int m=0; m<states; m++) fill(nxtDP[m].begin(), nxtDP[m].end(), NEG);
for(int mask=0; mask<states; mask++){
for(int used=0; used<=K; used++){
ll curVal = cur[mask][used];
if(curVal == NEG) continue;
for(auto &T : transArr[flag][mask]){
int newUsed = used + T.cnt;
if(newUsed > K) continue;
ll addSum = 0;
for(auto r : T.vert)
addSum += g[r][col] + g[r+1][col];
} code cua mik moi nguoi tham khao nha bai nay rat kho mik suy nghi ca dem moi ra