2012-09-03 10:13:55Morris
[ACM-ICPC][Asia - Daejeon] 5842 - Equipment
細想,
1. when k >= 5, n >= 5, 那麼裝備只有 5 種屬性, 只要抓每種屬性的最大值加總即可,
2. when k < 5, 則其中某一件裝備被抓來時, 套用的最加屬性會有 1~k 個之間, 也就是這 k 件會分別佔據 5 種屬性, 我們只要窮舉 5 種屬性分配給 k 件套用的可能, 然後進行跟 1. 一樣的 Greedy 即可。
1. O(5n)
2. O(5^k * n)
#include <stdio.h>
int n, k, ans;
int r[10001][5], reduce[5];
void dfs(int idx, int tk) {
int i, j;
if(idx == 5) {
int mm[5] = {}, tmp = 0;
for(i = 0; i < n; i++) {
int tm[5] = {};
for(j = 0; j < 5; j++)
tm[reduce[j]] += r[i][j];
for(j = 0; j < 5; j++)
mm[j] = mm[j] > tm[j] ? mm[j] : tm[j];
}
for(i = 0; i < 5; i++)
tmp += mm[i];
if(ans < tmp) ans = tmp;
return;
}
for(i = 0; i < tk; i++) {
reduce[idx] = i;
dfs(idx+1, tk);
}
}
int main() {
int t, i, j;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &k);
for(i = 0; i < n; i++) {
for(j = 0; j < 5; j++)
scanf("%d", &r[i][j]);
}
if(k >= 5) {
int ans = 0;
for(i = 0; i < 5; i++) {
int tmp = 0;
for(j = 0; j < n; j++) {
if(r[j][i] > tmp)
tmp = r[j][i];
}
ans += tmp;
}
printf("%d\n", ans);
} else {
ans = 0;
dfs(0, k);
printf("%d\n", ans);
}
}
return 0;
}
1. when k >= 5, n >= 5, 那麼裝備只有 5 種屬性, 只要抓每種屬性的最大值加總即可,
2. when k < 5, 則其中某一件裝備被抓來時, 套用的最加屬性會有 1~k 個之間, 也就是這 k 件會分別佔據 5 種屬性, 我們只要窮舉 5 種屬性分配給 k 件套用的可能, 然後進行跟 1. 一樣的 Greedy 即可。
1. O(5n)
2. O(5^k * n)
#include <stdio.h>
int n, k, ans;
int r[10001][5], reduce[5];
void dfs(int idx, int tk) {
int i, j;
if(idx == 5) {
int mm[5] = {}, tmp = 0;
for(i = 0; i < n; i++) {
int tm[5] = {};
for(j = 0; j < 5; j++)
tm[reduce[j]] += r[i][j];
for(j = 0; j < 5; j++)
mm[j] = mm[j] > tm[j] ? mm[j] : tm[j];
}
for(i = 0; i < 5; i++)
tmp += mm[i];
if(ans < tmp) ans = tmp;
return;
}
for(i = 0; i < tk; i++) {
reduce[idx] = i;
dfs(idx+1, tk);
}
}
int main() {
int t, i, j;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &k);
for(i = 0; i < n; i++) {
for(j = 0; j < 5; j++)
scanf("%d", &r[i][j]);
}
if(k >= 5) {
int ans = 0;
for(i = 0; i < 5; i++) {
int tmp = 0;
for(j = 0; j < n; j++) {
if(r[j][i] > tmp)
tmp = r[j][i];
}
ans += tmp;
}
printf("%d\n", ans);
} else {
ans = 0;
dfs(0, k);
printf("%d\n", ans);
}
}
return 0;
}