上午：
签到题 + dp
这里贴出dp代码。
题目描述：
给出 n m分别表示有n个英雄和m件装备
然后给出n*m的二维数组，第 i 行第 j 列表示第 i 个英雄拥有 j 件装备时候的攻击力
例子：
输入
2 3
5 6 7
7 8 9
输出
13
解释：第一个英雄拥有1个装备，战斗力为5，第二个英雄拥有2个装备，战斗力8， 8 + 5 = 13
问 n个英雄能够装备出的最大攻击力为多少
思路：
dp[ i ][ j ] i 代表第 i 个英雄 j 代表已经使用了多少装备
#include <bits/stdc++.h>
#define maxn 105
#define ll long long
using namespace std;
ll a[maxn][maxn];
int main(){
int n, m;
scanf("%d%d",&m, &n);
memset(a, 0, sizeof(a));
for(int i = 1; i<=m; i++){
for(int j = 1; j<= n; j++){
scanf("%lld", &a[i][j]);
}
}
ll dp[m + 1][n + 1];
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= m; i++){
for(int j = 0; j <= n; j++){
for(int k = 0 ; k <= j ;k++){
dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + a[i][k]);
}
}
}
ll ans = 0;
for(int i = 0; i <= n; i++){
ans = max(ans, dp[m][i]);
}
printf("%lld\n",ans);
}
下午：
下午就写了10几分钟。。。就做完了
签到题 + 贪心
这里贴出贪心代码
有n关卡
输出n行数据 ai bi
ai表示通过这关能获取到的分数，bi取值0或1,1代表可以让分数 * 2，但是不获取此关的分数，即ai；或者获取ai，放弃 * 2。
主角可以自己选择先通哪一关。
简单贪心，让bi 不为 1 的先去通关，如果为 1 ，则分数大的在前面。
#include <bits/stdc++.h>
#define maxn 105
#define ll long long
using namespace std;
struct knight{
ll a;
int b;
}p[maxn];
bool cmp(knight x, knight y){
if(x.b == y.b)
return x.a > y.a;
return x.b < y.b;
}
int main(){
int n,b;
ll a;
while(scanf("%d",&n)!=EOF){
ll point = 0;
for(int i = 0 ;i < n; i++){
scanf("%lld%d",&p[i].a,&p[i].b);
}
sort(p, p + n, cmp);
for(int i = 0 ; i < n; i++){
if(p[i].b == 1){
point = max(point * 2, point + p[i].a);
}else{
point += p[i].a;
}
}
printf("%lld\n",point);
}
return 0;
}
全部评论
(4) 回帖