题解 | #神秘餐馆#

从通过代码来看，本题隐含了条件： 1.必须连着吃，不可以隔一天或者几天不吃。

首先我们根据题意可知，应该分为两个部分来讨论，一个是7天以内的情况， 一个7天以后的情况。 在7天以内，可以根据贪心，哪道菜最便宜就吃哪道。 7天以后，因为题目要求菜品选择绑定的关系，所以，要重新考虑选择哪道菜。

以第三个数据用例举例：

第一天和第八天有菜品绑定的关系，所以我们可以维护第（i%7+1）天(0<=i<n)选择第j（0<=j<m）道菜的价格，以便于我们贪心的选择第（i%7+1）天的菜品。 同时，由于我们更换了菜品的选择，那么之前选择的菜品所花费的费用也应该反悔掉。 因为只需要知道上一次（周期性）的选择花费了多少钱，所以我们可以维护周期性的上一次花费的费用：lastcost[7];表示第i-7天，我们选择菜品花费的费用（菜品绑定）。 然后当费用超出预算，那么第i-1天一定是我们能吃的最后一天。(在我的代码实现中，由于i是从0开始的，所以不需要再进行i-1这个操作了）

#include<bits/stdc++.h>
using namespace std;

void print(vector<vector<int>>& arr)
{
    for(int i=0;i<arr.size();++i)
    {
        for(int j=0;j<arr[0].size();++j)
        {
            cout<<arr[i][j]<<" ";
        }
        cout<<endl;
    }
}


void solve()
{
  ios::sync_with_stdio,cin.tie(0),cout.tie(0);
  int n,m,budget;
  cin>>n>>m>>budget;
  vector<vector<int>> prices(n,vector<int>(m));

  for(int i=0;i<n;++i)
  {
    for(int j=0;j<m;++j)
    {
      char c;
      cin>>c;
      if('0'<=c&&c<='9') prices[i][j]=c-'0';
      else if('A'<=c&&c<='Z') prices[i][j]=c-'A'+10;
      else if('a'<=c&&c<='z') prices[i][j]=c-'a'+36;
    }
  }

//   print(prices);
  vector<vector<int>> round_cost(7,vector<int>(m,0));//维护每个周期的选择结果，以便于贪心选择(怎么吃)。
  vector<int> day_prices(m);//每天花费
  int sum=0;//累积花费
  vector<int> lastcost(7,0);//需要反悔的花费；
  for(int i=0;i<n;++i)
  {


    //维护当前周期的贪心选择（最小花费选择）;第i%7个周期，选择第j道菜的总花费最低。
    int mincost=INT_MAX;
    
    //第i天的每种选择的对当前周期花费的影响；
    for(int j=0;j<m;++j)
    {
        round_cost[i%7][j]+=prices[i][j];
        mincost=min(mincost,round_cost[i%7][j]);
    }
    

    if(i<7)//小于7天，那么简单贪心的选择即可。
    {
        sum+=mincost;
        
    }
    else//大于7天，需要从周期绑定后的数据结构中选择贪心。
    {
        sum+=mincost-lastcost[i%7];
    }
    lastcost[i%7]=mincost;
    if(sum>budget)
    {
        cout<<i<<endl;
        break;
    }
  }
  if(sum<=budget)
  cout<<n<<endl;
}



int main()
{
  solve();
  return 0;
}