1042 最低票价

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

// leetcode 983 Minimum Cost For Tickets.
// https://leetcode.com/problems/minimum-cost-for-tickets/

int func(int days[], int costs[], int len, int n_costs)
{
    // dp[i]表示前i天旅行的费用
    int dp[366];
    for(int i=0;i<366;i++)
    {
        dp[i] = INT_MAX;
    }
    // 前0天，没有旅行，没有费用
    dp[0] = 0;
    // 扫描days数组的下标
    int idx = 0;
    for(int i=1;i<366;i++)
    {
        // 第i天不旅行，防止idx下标出界
        // idx>=len必须放在前面，先进行判断，否则会造成缓冲区溢出
        if(days[idx] != i || idx>=len)
        {
            // 费用和之前保持不变
            dp[i] = dp[i-1];
        }
        // 第i天旅行
        else
        {
            // 三种费用依次比较，注意防止i-1，i-7，i-30出了边界
            dp[i] = min(dp[i], ( i>=1 ? dp[i-1] : 0 ) + costs[0]);  // 一天的费用
            dp[i] = min(dp[i], ( i>=7 ? dp[i-7] : 0) + costs[1]);  // 七天的费用
            dp[i] = min(dp[i], ( i>=30 ? dp[i-30] : 0) + costs[2]);  // 一个月的费用
            // 下一次旅行的日期
            idx++;
        }
    }
    return dp[365];
}

int main()
{
    const int n_costs = 3;
    int n_test;
    cin>>n_test;
    for(int i=0;i<n_test;i++)
    {
        int len;
        cin>>len;
        int days[len];
        int costs[n_costs];
        for(int j=0;j<len;j++)
        {
            cin>>days[j];
        }
        for(int j=0;j<n_costs;j++)
        {
            cin>>costs[j];
        }
        cout<<func(days, costs, len, n_costs)<<endl;
    }
}