HOJ Recoup Traveling Expenses(最长递减子序列变形)

A person wants to travel around some places. The welfare in his company can cover some of the airfare cost. In order to control cost, the company requires that he must submit the plane tickets in time order and the amount of the each submittal must be no more than the previous one. So he must arrange the travel plan according to the airfare cost. The more amount of cost covered with the welfare, the better. If the reimbursement is the same, the more times of flights, the better.

For example, he's route is like this: G -> A-> B -> C -> D -> E -> G, and the quoted price between each destination are as follows:

 G -> A: 500
 A -> B: 300
 B -> C: 700
 C -> D: 200
 D -> E: 400
 E -> G: 100

So if he flies from in the order: B -> C, D -> E, E -> G, the reimbursement should be: 

700 + 400 + 100 = 1200 (Yuan)

If the airfare from B to C goes down to 600 Yuan, according to the routine, the reimbursement should be 1100 Yuan. But if he chooses to travel from G -> A, A -> B, C -> D, E -> G, the reimbursement should be: 

500 + 300 + 200 + 100 = 1100 (Yuan)

But in this way, he gets one more flight, so this is a better plan.

Input

The input includes one or more test cases. The first data of each test case is N (1 <= N <= 100), followed by N airfares. Each airfare is integer, between 1 and 224.

Output

For one test case, output two numbers P and Q. P is the most amount of reimbursement fee. Q is the most times of flights under the circumstances of P.

Sample Input

1 60
2 60 70
3 50 20 70

Sample Output

60 1
70 1
70 2
在求最长递减子序列的基础上变形一下,
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>

using namespace std;
int n;
int dp[105];
int bp[105];
int sp[105];
int a[105];
int ans1,ans2,ans;
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);

        memset(dp,0,sizeof(dp));
        memset(bp,0,sizeof(bp));
        memset(sp,0,sizeof(sp));
        ans1=0;ans2=0;ans=0;
        for(int i=1;i<=n;i++)
        {
            int num1=0;
            int num2=0;

            for(int j=i-1;j>=1;j--)
            {
                if(a[i]<=a[j])
                {
                    if(num1<dp[j]||(num1==dp[j]&&num2<bp[j]))
                    {
                        num1=dp[j];
                        num2=bp[j];
                    }
                }
            }
            dp[i]=num1+a[i];
            bp[i]=num2+1;
            if(ans1<dp[i]||(ans1==dp[i]&&ans2<bp[i]))
            {
                ans1=dp[i];
                ans2=bp[i];
            }

        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

初学自学编程,从什么语言开始起步比较好?

自学编程如果是兴趣方面的可以选择比较简单的入门语言入手,然后再慢慢切入到新的编程语言,目前相对来说比较好入门的编程语言是python,这门语言的集成度非常高,适...

37950
来自专栏Crossin的编程教室

身份证号码校验算法

1、数字含义 中国大陆第二代身份证号码由18位数据或字母组成,每位数据都有特定的含义,结果如下: ? 每组数字都有不同的含义: 第1至2位数字代表所在省(直辖市...

61290
来自专栏MixLab科技+设计实验室

设计中的类比思维与人工智能的图像类比算法

这篇属于论文解读系列,往期写过一篇关于平面设计作品视觉焦点识别的论文解读,本期解读下《Deep Visual Analogy-Making》这篇论文。 ? 有没...

37140
来自专栏MixLab科技+设计实验室

从低保真原型中生成前端代码

今天聊下《 技术 Mix 设计 》的话题。技术与设计两者的边界,越来越模糊,从用机器视觉判断平面设计作品的视觉焦点,到用深度学习指导用户体验设计,还有用深度学习...

36460
来自专栏小樱的经验随笔

遗传算法详解(LINGO及MatlabGA工具箱求解实现)

遗传算法 1.前言 遗传算法是一种基于生物界自然群体遗传进化机制的自适应全局优化概率搜索算法。它与传统算法不同,不依赖梯度信息,而是通过模拟自然进化过程来搜索最...

2.7K70
来自专栏计算机视觉战队

在单机上快速、精确的100000类别的检测

今天带来的这篇推送,估计您有读过或试验过,但是为了让更多的科研学者知道这么“牛”的内容知识,接下来就开始说说今天的主题——1000000类的快速精确检测。 注:...

31360
来自专栏MixLab科技+设计实验室

算法驱动型的设计

“Everything should be made as simple as possible, but not simpler” — Albert Eins...

38170
来自专栏程序员互动联盟

算法好等同于编程能力强吗?

算法和编程不是同等而言,学好编程包含层面很多,基础的编程语言,良好的逻辑思维能力(算法算是包含在这个层面),编程最核心的是编程思想。 相比而言算法是编程基础里面...

40050
来自专栏Python爬虫与算法进阶

来codewars与我一起玩耍吧

先看一道题目 如何使用代码表示“石头、剪刀、布”之间的关系。 即:石头 > 剪刀,剪刀 > 布, 剪刀 > 布 当时我想了很多,构造一个字典,和数字对应,但是...

376100
来自专栏应兆康的专栏

强大的位运算

什么是位运算? 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。比如,and运算本来是一个逻辑运算...

35060

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励