求帮忙做到题！谢谢谢谢！

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3202 天前的主题，其中的信息可能已经有所发展或是发生改变。

一道买车票的题

车票有 3 种

1 。一天的票，价格 2
2.7 天的票，价格 7 （当天买，在当天+6 天内有效）
3 。 30 天的票，价格 25

写一个方法，参数是一个 int[] dates

这个 dates 里的每一个元素是这个月几号你要坐车要买票。

算出最便宜的买票的总价格。

public int solution(int[] dates) {
// 返回最便宜买票方法的总价格
}

假设下个月 3 月有 31 天。

那这个 dates 最多就是 31 个元素， 0 - 30

我 1 号， 2 号， 4 号， 5 号， 7 号， 29 号， 30 号买票
dates[0] = 1
dates[1] = 2
dates[2] = 4
dates[3] = 5
dates[4] = 7
dates[5] = 29
dates[6] = 30

那最便宜的就是买一张 7 天票，从 1 号到 7 号，加上 29 号， 30 号买两张 1 天票，一共 7+4 = 11 元

dates

int

票

车票

14 条回复 • 2016-02-11 16:08:43 +08:00

ttma1046

2016-02-06 13:56:55 +08:00

求帮忙。

pimin

2016-02-06 14:12:17 +08:00 via Android

这个类似公交卡嘛
按照你的思路来：
1.7 天卡要达到搜 4 个元素才划算，凑＞ 4 的买 7 天卡；
2.剩下元素全部买单日卡，计算总价 s1 ；
3.s1 和月卡比价格

yuriko

2016-02-06 14:15:36 +08:00

@ttma1046 动规吧……
一个数组记录结算到第 i 天时的最低价格，然后第 n 天就是 m[n-7]+7 ， m[n-30]+25 ， m[n-1]+2,m[n-1]中间能满足当天票需求的最小值，类推完 30 天得解

ttma1046

2016-02-06 14:22:52 +08:00

@pimin 这是就是我写的，写得很垃圾。惨不忍睹

ttma1046

2016-02-06 14:24:11 +08:00

@yuriko 谢谢，能不能在详细的说点。动规我早就还给大学老师了。

yuriko

2016-02-06 14:31:21 +08:00

@ttma1046 我还觉得说的太细了……
m[i]表示第 i 天为止的最低支出票价
m[0]=0 开始，目标得到 m[31]
for i=1~31
if （第 i 天需要票）{m[i] = min(m[i-7]+7 ， m[i-30]+25 ， m[i-1]+2)}//注意越界取 0 即可
else{m[i]=n[i-1]}

基本思路就是这样不知道有没有错

ttma1046

2016-02-06 14:47:08 +08:00

@yuriko 你的是不是每天都要买票？题目是随机抽几天出来要去买票坐车，也能这样做吗？

ilotuo

2016-02-06 14:55:17 +08:00

2 楼就有答案了..
遍历 data.length -4 次
(data[i+3]-data[i])<7 买 7 天票

yuriko

2016-02-06 15:24:18 +08:00

@ttma1046 你认真读一下逻辑好么，那个 if 语句你有看到么……

3pointer

2016-02-06 15:25:17 +08:00

2 楼的意思是没错，但是这样考虑问题就复杂了。
比如 1 ， 5 ， 6 ， 7 ， 8 ， 9 肯定是不凑前四个而是后五个。
3 楼已经给出了简单的解法，遍历一遍就行了

ttma1046

2016-02-07 06:09:31 +08:00

@yuriko @3pointer
写的很垃圾,求拍砖

public int solution(int[] selectiveDates)
{
int [] minCost = new int[31];

for (int date = 0; date < 31; date++)
{
int oneDayAgo = 0;
if (date - 1 > 0)
oneDayAgo = date - 1;

if (selectiveDates.Contains(date))
{
int sevenDaysAgo = 0;
if (date - 7 > 0)
sevenDaysAgo = date - 7;

int thirtyDaysAgo = 0;
if (date - 30 > 0)
thirtyDaysAgo = date - 30;

minCost[date] = Math.Min(minCost[sevenDaysAgo] + 7, minCost[thirtyDaysAgo] + 25);
minCost[date] = Math.Min(minCost[date], minCost[oneDayAgo] + 2);
}
else
{
minCost[date] = minCost[oneDayAgo];
}
}

return minCost[30];
}

ttma1046

2016-02-07 06:09:58 +08:00

```csharp
public int solution(int[] selectiveDates)
{
int [] minCost = new int[31];

for (int date = 0; date < 31; date++)
{
int oneDayAgo = 0;
if (date - 1 > 0)
oneDayAgo = date - 1;

if (selectiveDates.Contains(date))
{
int sevenDaysAgo = 0;
if (date - 7 > 0)
sevenDaysAgo = date - 7;

int thirtyDaysAgo = 0;
if (date - 30 > 0)
thirtyDaysAgo = date - 30;

minCost[date] = Math.Min(minCost[sevenDaysAgo] + 7, minCost[thirtyDaysAgo] + 25);
minCost[date] = Math.Min(minCost[date], minCost[oneDayAgo] + 2);
}
else
{
minCost[date] = minCost[oneDayAgo];
}
}

return minCost[30];
}
```

sengxian

2016-02-11 16:05:54 +08:00

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
bool need[31 + 1]; //需要初始化
int dp[31 + 1];
dp[0] = 0; //边界
for(int i = 1; i <= 31; ++i) {
dp[i] = dp[i - 1] + 2; //总可以买一天的票
if(!need[i]) dp[i] = dp[i - 1];
else dp[i] = min(dp[i], min(dp[i - 7 < 0 ? 0 : i - 7] + 7, dp[i - 30 < 0 ? 0 : i - 30] + 25));
}
return 0;
}

sengxian

2016-02-11 16:08:43 +08:00