小明有n(1≤n≤2000）个美味的食物，他想卖掉它们来赚钱。这些食物放在一些箱子里，它们有些有趣的特性：
（1）这些食物被编号1~n，每一天小明可以从这排箱子的头部或者尾部取出食物去卖；
（2）这些食物放的越久，年龄越大，价值越大，食物i有一个初始的价值V(i);
（3）放了a天后，年龄为a，食物最终价值为V(i)xa。
给定每一个食物的初始价值V(i)，请求出小明卖掉它们后可以获得的最大价值，第一天出售的食物年龄为1，此后每增加一天食物的年龄就加1。
[编程题]小明卖食物
这题的测试用例有误。
我用动态规划写完提交之后WA，我想了很久没有想出哪里错了，就看了通过的网友的代码，发现用的是贪心：在任意一天，如果还没卖完，在剩下的食物中，两端的哪个价值小就把哪个卖掉。
但是这对于这个输入[8, 2, 6, 7, 1]就会得到错误的解。用贪心法，依次卖掉1, 7, 6, 2, 8，总的收入将会是1 * 1 + 2 * 7 + 3 * 6 + 4 * 2 + 5 * 8 = 81；而如果按1, 8, 2, 6, 7的顺序来卖，总收入是1 * 1 + 2 * 8 + 3 * 2 + 4 * 6 + 5 * 7 = 82，可见这题用贪心是不行的。
附本人的动态规划解法：
#include <stdio.h>
#define MAX_N 2000
int value[MAX_N], dp[MAX_N];
int max(int x, int y)
{
return x > y ? x : y;
}
int solve(int n)
{
int i, j, age;
for (i = 0; i < n; ++i)
{
dp[i] = n * value[i];
}
for (i = n - 2; i >= 0; --i)
{
for (j = i + 1; j < n; ++j)
{
age = n - j + i;
dp[j] = max(value[i] * age + dp[j],
value[j] * age + dp[j - 1]);
}
}
return dp[n - 1];
}
int main(int argc, char const *argv[])
{
int n, i;
scanf("%d", &n);
for (i = 0; i < n; ++i)
{
scanf("%d", value + i);
}
printf("%d\n", solve(n));
return 0;
}
编辑于 2019-02-08 14:26:01
回复(5)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,res=0;
cin>>n;
int v[n];
for(int i=0;i<n;i++)
cin>>v[i];
int head = 0;
int tail = n - 1;
int sum = 0;
int day = 1;
while (head <= tail)
{
if (v[head] < v[tail])
sum += day * v[head++];
else
sum += day * v[tail--];
day++;
}
cout<<sum<<endl;
return 0;
}
发表于 2019-06-25 21:45:55
回复(0)
双指针（JAVA）
用两个指针指向头尾，每次都取较小值加上去。因为要获得最大值而且每次只能操作头尾，所以较大的值放在后面计算肯定会取得最优解。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] v = new int[n];
for (int i = 0; i < n; i++) {
v[i] = sc.nextInt();
}
int head = 0;
int tail = n - 1;
int sum = 0;
int day = 1;
while (head <= tail) {
if (v[head] < v[tail]) {
sum += day * v[head++];
} else {
sum += day * v[tail--];
}
day++;
}
System.out.println(sum);
}
}
发表于 2019-06-12 23:33:12
回复(0)
//java双端队列
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int a = in.nextInt();
Deque<Integer> deque = new LinkedList<>();
for(int i=0;i<a;i++) deque.offerLast(in.nextInt());
System.out.println(caculate(deque));
}
}
public static int caculate(Deque<Integer> deque){
int sum = 0,day = 1;
while(!deque.isEmpty()){
if(deque.peekFirst() < deque.peekLast()){
sum += day * deque.pollFirst();
day ++;
}else{
sum += day * deque.pollLast();
day ++;
}
}
return sum;
}
}
发表于 2021-07-25 16:56:36
回复(0)
#include<iostream>
#include<vector>
int main()
{
int n,v;
while(std::cin>>n)
{
std::vector<int>s;
for(int i=0;i<n;i++)
{
std::cin>>v;
s.push_back(v);
}
int count=0;
for(int i=1;i<=n-1;i++)
{
if(s[0]<s[s.size()-1])
{
count+=s[0]*i;
s.erase(s.begin());
}
else if(s[0]>s[s.size()-1])
{
count+=s[s.size()-1]*i;
s.pop_back();
}
else if(s[0]==s[s.size()-1]&&s[1]<=s[0])
{
count+=s[0]*i;
s.erase(s.begin());
}
else if(s[0]==s[s.size()-1]&&s[s.size()-2]<=s[0])
{
count+=s[0]*i;
s.pop_back();
}
else continue;
}
count+=s[0]*n;
std::cout<<count<<std::endl;
}
return 0;
}
#include<vector>
int main()
{
int n,v;
while(std::cin>>n)
{
std::vector<int>s;
for(int i=0;i<n;i++)
{
std::cin>>v;
s.push_back(v);
}
int count=0;
for(int i=1;i<=n-1;i++)
{
if(s[0]<s[s.size()-1])
{
count+=s[0]*i;
s.erase(s.begin());
}
else if(s[0]>s[s.size()-1])
{
count+=s[s.size()-1]*i;
s.pop_back();
}
else if(s[0]==s[s.size()-1]&&s[1]<=s[0])
{
count+=s[0]*i;
s.erase(s.begin());
}
else if(s[0]==s[s.size()-1]&&s[s.size()-2]<=s[0])
{
count+=s[0]*i;
s.pop_back();
}
else continue;
}
count+=s[0]*n;
std::cout<<count<<std::endl;
}
return 0;
}
发表于 2020-09-13 10:26:47
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.nextLine();
int num = Integer.parseInt(string);
int[] arr = new int[num];
for(int i = 0; i < num; i++) {
string = scanner.nextLine();
arr[i] = Integer.parseInt(string);
}
greedSell(arr, num);
}
//贪心思想，每次左右两端判断卖价值小的那个
public static void greedSell(int[] arr, int n) {
int value = 0;
int leftIndex = 0;
int rightIndex = n-1;
int day = 1;
while(leftIndex != rightIndex) {
if(arr[leftIndex] <= arr[rightIndex]) {
value+=arr[leftIndex] * day;
leftIndex ++;
}else {
value+=arr[rightIndex] * day;
rightIndex--;
}
day++;
}
value+=arr[leftIndex] * day;
System.out.println(value);
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.nextLine();
int num = Integer.parseInt(string);
int[] arr = new int[num];
for(int i = 0; i < num; i++) {
string = scanner.nextLine();
arr[i] = Integer.parseInt(string);
}
greedSell(arr, num);
}
//贪心思想，每次左右两端判断卖价值小的那个
public static void greedSell(int[] arr, int n) {
int value = 0;
int leftIndex = 0;
int rightIndex = n-1;
int day = 1;
while(leftIndex != rightIndex) {
if(arr[leftIndex] <= arr[rightIndex]) {
value+=arr[leftIndex] * day;
leftIndex ++;
}else {
value+=arr[rightIndex] * day;
rightIndex--;
}
day++;
}
value+=arr[leftIndex] * day;
System.out.println(value);
}
}
为啥提交不通过，数组越界？？？虽然我觉得一楼说的对，但是我还是只是想得分。。。
测试了好多遍，难道不是用贪心思想？
加了好多换行，空格还是不行。。。我还是放弃了
谁帮我看一下呀，跑起来完全没问题呀
***感觉自己是bug之神，**。。。
编辑于 2019-04-25 14:57:27
回复(0)
#include <iostream>
using namespace std;
int main ()
{
int n;
cin>>n;
int *p;
p=new int[n];
for(int i=0;i<n;i++)
{
cin>>p[i];
}
int *q;
q=new int[n];
int i=0,j=n-1,k=0;
while(i<=j)
{
if(p[i]<=p[j])
{
q[k]=p[i];
k++;
i++;
}
else
{
q[k]=p[j];
k++;
j--;
}
}
int val=0;
for(int i=0;i<n;i++)
{
val+=q[i]*(i+1);
}
cout<<val;
return 0;
}
发表于 2019-03-23 15:46:07
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
