Untitled
unknown
plain_text
a year ago
4.0 kB
8
Indexable
#include<iostream> using namespace std; int T, M, N; int arr[20][20], visited[20][20]; int Answer; // -1 0, 0 1, 1 1, 1 0, 1 -1, 0 -1 // -1 0, -1 1, 0 1, 1 0, 0 -1, -1 -1; int dxc[6] = {-1, 0, 1, 1, 1, 0}; int dyc[6] = {0, 1, 1, 0, -1, -1}; int dxl[6] = {-1, -1, 0, 1, 0, -1}; int dyl[6] = {0, 1, 1, 0, -1, -1}; bool isValid(int x, int y){ return x >= 1 && x <= N && y > 0 && y <= M; } void bt(int x, int y, int sum, int count){ if(count == 4){ if(Answer < sum){ Answer = sum; } return; } for(int i = 0; i < 6; i++){ if(y % 2 == 0){ int nx = x + dxc[i]; int ny = y + dyc[i]; if(isValid(nx, ny) && visited[nx][ny] == 0 ){ visited[nx][ny] = 1; bt(nx, ny, sum+ arr[nx][ny], count+1); bt(x,y,sum+arr[nx][ny],count+1); visited[nx][ny] = 0; } } else{ int nx = x + dxl[i]; int ny = y + dyl[i]; if(isValid(nx, ny) && visited[nx][ny] == 0){ visited[nx][ny] = 1; bt(nx, ny, sum+ arr[nx][ny], count+1); bt(x,y,sum+arr[nx][ny],count+1); visited[nx][ny] = 0; } } } } void reset(){ for(int i = 1; i <= N; i++){ for(int j = 1; j <= M; j++){ visited[i][j] = 0; } } } int main(){ freopen("input.txt", "r", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ Answer = 0; cin >> M >> N; for(int i = 1; i <= N; i++){ for(int j = 1; j <= M; j++){ cin >> arr[i][j]; } } for(int i = 1; i <= N; i++){ for(int j = 1; j <= M; j++){ visited[i][j] = 1; int sum = arr[i][j]; bt(i, j, sum, 1); reset(); } } cout << "Case #" <<tc << endl; cout << long( Answer * Answer) << endl; } return 0; } // 5 5 3 300 410 150 55 370 120 185 440 190 450 165 70 95 420 50 5 5 356 55 41 453 12 401 506 274 506 379 360 281 421 311 489 425 74 276 371 164 138 528 461 477 470 Case #1 2250000 Case #2 3748096 ======================================== #include <iostream> using namespace std; int n,m,k; int marketPrice[25]; int sales[35][25]; int need[25]; int have[25]; int res; bool check(int idx, int item) { for (int i = 0; i < sales[idx][1]; i++) { if (sales[idx][i+2] == item) return true; } return false; } void solve(int idx, int cost) { if (idx == k) { res = cost < res ? cost : res; return; } if (cost >= res) return; if (have[need[idx]] >= 1) solve(idx+1,cost); have[need[idx]]++; solve(idx+1,cost+marketPrice[need[idx]]); have[need[idx]]--; for (int i = 0; i < m; i++) { if (check(i,need[idx])) { for (int j = 0; j < sales[i][1]; j++) { have[sales[i][j+2]]++; } solve(idx+1,cost+sales[i][0]); for (int j = 0; j < sales[i][1]; j++) { have[sales[i][j+2]]--; } } } } int main() { //freopen("input.txt","r",stdin); int T; cin >> T; for (int tc = 1; tc <= T; tc++) { cin >> n; for (int i = 1; i <= n; i++) { cin >> marketPrice[i]; have[i] = 0; } cin >> m; for (int i = 0; i < m; i++) { cin >> sales[i][0] >> sales[i][1]; for (int j = 0; j < sales[i][1]; j++) { cin >> sales[i][j+2]; } } cin >> k; for (int i = 0; i < k; i++) { cin >> need[i]; } res = 999999; solve(0,0); cout << "#" << tc << " " << res << endl; } return 0; } Input 1 <-- T = 1, 5 <-- Số linh kiện chính của máy tính 20 15 17 18 25 <-- giá chợ Trời của 5 thiết bị từ 1 đến 5 tương ứng 4 <-- 4 gói ưu đãi trên mạng 30 3 1 2 5 <-- gói thứ nhất có giá 30, gồm 3 linh kiện 1, 2, 5 25 2 2 3 <-- gói thứ 2 có giá 25, gồm 2 linh kiện 2, 3 35 3 1 3 5 <-- gói thứ 3 có giá 35, gồm 3 linh kiện 1, 3, 5 20 2 3 4 <-- gói thứ 4 có giá 20, gồm 2 linh kiện 3, 4 3 2 4 5 <-- Số lượng anh Kim cần là 3, lần lượt là 2, 4, 5 Output #1 48
Editor is loading...
Leave a Comment