1221. 数字游戏
解题思路:
题目有个地方,我理解错了,导致WA很多次,问题是当你擦除a[i]时,你要将它对应的b[i]去减剩余的序列,之前一直以为第i轮就减去b[i],ORZ。
简单的动态,dp[i]表示去到第i轮时的最大擦出和。
按照我们直观的思路,肯定是最大消费的(也就是b[i]比较大的)应该先拿掉,因此我们先按照cost排序。
dp[j] = min{dp[j-1] + nodes[i].v - nodes[i].cost*(j-1)};
源码如下:
/*
* main.cpp
*
* Created on: Sep 23, 2011
* Author: raphealguo
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXL 210
struct Node{
int value;
int cost;
};
bool cmp(Node a, Node b){
return a.cost > b.cost;
}
int main(){
int n, m;
Node nodes[MAXL];
int i, j;
int dp[MAXL];
while (scanf("%d %d", &n, &m) != EOF){
memset(nodes, 0, sizeof(nodes));
memset(dp, 0, sizeof(dp));
for (i = 0; i < n; ++i){
scanf("%d", &nodes[i].value);
}
for (i = 0; i < n; ++i){
scanf("%d", &nodes[i].cost);
}
sort(nodes, nodes+n, cmp);
for (i = 0; i < n; ++i){
for (j = m; j >= 1; --j){
if (dp[j] < dp[j-1] + nodes[i].value - nodes[i].cost*(j-1)){
dp[j] = dp[j-1] + nodes[i].value - nodes[i].cost*(j-1);
}
}
}
printf("%d\n", dp[m]);
}
}
附带原题:
1221. 数字游戏
Description
小
W
发明了一个游戏,他在黑板上写出了一行数字
a1,a2,….an
,然后给你
m
个回合的机会,每回合你可以从中选择一个数擦去它,接着剩下来的每个数字
ai
都要递减一个值
bi
。如此重复
m
个回合,所有你擦去的数字之和就是你所得到的分数。
小
W
和他的好朋友小
Y
玩了这个游戏,可是他发现,对于每个给出的
an
和
bn
序列,小
Y
的得分总是比他高,所以他就很不服气。于是他想让你帮他算算,对于每个
an
和
bn
序列,可以得到的最大得分是多少。这样他就知道有没有可能超过小
Y
的得分。
Input
第一行,一个整数
n
(
1<=n<=200
),表示数字的个数。
第二行,一个整数
m
(
1<=m<=n
),表示回合数。
接下来一行有
n
个不超过
10000
的正整数,
a1,a2…an
,表示原始数字
最后一行有
n
个不超过
500
的正整数,
b1,b2….bn
,表示每回合每个数字递减的值
Output
一个整数,表示最大可能的得分
Sample Input
3
3
10 20 30
4 5 6
Sample Output
47
Problem Source
ZSUACM Team Member
分享到:
相关推荐
sicily部分源代码,全都亲测,可通过
中大sicily online judge的刷题指南,里面介绍得很详细,不过,最近sicily好像不能外网访问了。
sicily 1562_LVM.cpp参考代码
112页的大礼包,sicily的部分ac代码。
本cpp是sicily的1006的解题代码 这份代码以最简单的方式实现了它的功能要求 值得学习一番
Sicily的题目分类:各种题目的分类,大致方法,以及题目难度规范
sicily1007题答案,附代码解释,可以在平台上通过
本程序是中山大学sicily上1200-1221-1298-1324-1325的参考代码。
sicily 1274的AC源码,通过且速度快,适合学生使用
对于二叉树T,可以递归定义它的先序遍历、中序遍历和后序遍历如下: PreOrder(T)=T的根节点+PreOrder(T的左子树)+PreOrder(T的右子树) InOrder(T)=InOrder(T的左子树)+T的根节点+InOrder(T的右子树) PostOrder(T)=...
中山大学 ACM sicily 1294 题目代码
本程序解决了Sicily平台上Queue的问题,有较好的可读性
sicily(soj) 1022 1064 1310 1740 1876 1934 六题的源代码(数据结构综合应用题)
sicily 1817和1818的程序,各有两种方法,供参考。
本程序是中山大学sicily 1004-1007-1010-1014-1021 参考代码
本程序是中山大学sicily-1137-1145-1146-1147-1154-1157-1194的代码
包括 sicily online judge 1149等部分题目,线性表,最小生成树,中缀转后缀并计算后缀表达式等。
此处是sicily 1093,1888 c++的源代码
Sicily Online Judge,原题代码