LeetCode-983.最低票价_leecode maxtickes

题目：

代码：

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int cost[366];
        for(int i=0;i<366;i++) cost[i]=INT_MAX;
        for(int i=0;i<days.size();i++) cost[days[i]]=1;
        cost[365]=cost[365]==1?costs[0]:0;
        for(int i=364;i>0;i--){
            if(cost[i]==INT_MAX) cost[i]=cost[i+1];
            else{
                if(i+1<=365) cost[i]=cost[i+1]+costs[0];
                if(i+7<=365) cost[i]=min(cost[i],cost[i+7]+costs[1]);
                if(i+30<=365) cost[i]=min(cost[i],cost[i+30]+costs[2]);
            }
        }
        return cost[1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

榜首：

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> cost(366,0);
        vector<int> d(366,0);
        int j=0;
        for(auto dd:days)
            d[dd]++;
        for(int i=1;i<366;++i){
            cost[i] = cost[i-1];
            if(d[i]==1){
                j++;
                cost[i] += costs[0];
            }
        }
        for(int i=1;i<366;++i){
            if(d[i]==1){
                cost[i] = min(cost[i],cost[i-1]+costs[0]);
                if(i<7)
                    cost[i] = min(cost[i],costs[1]);
                else
                    cost[i] = min(cost[i],cost[i-7]+costs[1]);
            }
            else{
                cost[i] = min(cost[i],cost[i-1]);
            }
        }
        for(int i=1;i<366;++i){
            if(d[i]==1){
                cost[i] = min(cost[i],cost[i-1]+costs[0]);
                if(i<7)
                    cost[i] = min(cost[i],costs[1]);
                else
                    cost[i] = min(cost[i],cost[i-7]+costs[1]);
                if(i<30)
                    cost[i] = min(cost[i],costs[2]);
                else
                    cost[i] = min(cost[i],cost[i-30]+costs[2]);
            }
            else{
                cost[i] = min(cost[i],cost[i-1]);
            }
        }
        return cost[365];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46