NC14713. 勇敢的妞妞
描述
美丽的牛家庄受到了外星人的侵略, 勇敢的妞妞要上战场抵御侵略。
在妞妞上战场前, 村长牛牛给了妞妞N件装备, 妞妞需要选择其中的K件,装备在身上提升自己的战斗力。每件装备有5种属性增幅值,对于第i件装备它的属性增幅值为(ri1, ri2, ri3, ri4, ri5), 分别代表该装备对不同的属性值增幅。
当妞妞装备多件装备的时候,由于装备之前会互相影响, 对于每种属性值的增幅并不是所有装备该属性值之和, 而是该种属性值下所有装备中最大的属性值。而妞妞最终增加的战斗力为这5种属性值增幅之和。
妞妞一定要保卫牛家庄, 所以她希望她能提升尽可能多的战斗力, 请你帮帮她计算她最多能增加多少战斗力。
输入描述
输入包括N+1行,
第一行包括两个正整数N和K(1 <= N <= 10000, 1 <= K <= N), 分别表示一共有的装备数量和妞妞需要选择的装备数量。
接下来的N行,每行5个整数ri1, ri2, ri3, ri4, ri5 (0 <= ri1, ri2, ri3, ri4, ri5 <= 10000)表示第i件装备的5种属性值增幅。
输出描述
输出一个整数,表示妞妞最多能增加的战斗力。
示例1
输入:
4 2 30 30 30 30 0 50 0 0 0 0 0 50 0 50 10 0 0 50 0 20
输出:
170
说明:
妞妞要从4件装备中选取2件, 如果妞妞选择第1件和第3件装备,那么增加的战斗力为30 + 50 + 30 + 50 + 10 = 170, 这是最大的方案。C 解法, 执行用时: 45ms, 内存消耗: 1576K, 提交时间: 2022-12-07 15:44:46
#include<stdio.h>
//#include<stdbool.h>
#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))
#define N 120000
int n,m;
int a[N][32];
int f[5][32];
int main()
{
int i,j,s,x,k,l;
scanf("%d %d",&n,&m);
if(m>=5)
m=5;
for(i=1;i<=n;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&x);
for(s=0;s<32;s++)
if(s&(1<<j))
a[i][s]+=x;
}
}
for(i=1;i<=m;i++)
for(j=0;j<32;j++)
for(k=0;k<32;k++)
{
if((j&k)!=k)
continue;
for(l=1;l<=n;l++)
{
f[i][j]=max(f[i-1][j^k]+a[l][k],f[i][j]);
}
}
printf("%d",f[m][31]);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 60ms, 内存消耗: 2020K, 提交时间: 2020-02-29 20:54:20
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define N 120000
int n,m;
int a[N][32];
int f[5][32];
int main()
{
cin>>n>>m;
if(m>=5) m=5;
for(int i=1,x;i<=n;i++)
{
for(int j=0;j<5;j++)
{
cin>>x;
for(int s=0;s<32;s++)
if(s&(1<<j)) a[i][s]+=x;
}
}
for(int i=1;i<=m;i++)
for(int j=0;j<32;j++)
for(int k=0;k<32;k++)
{
if((j&k)!=k) continue;
for(int l=1;l<=n;l++)
{
f[i][j]=max(f[i-1][j^k]+a[l][k],f[i][j]);
}
}
cout<<f[m][31]<<endl;
return 0;
}