C++에서 요리 줄이기

<시간/>

요리사가 있다고 가정해 봅시다. 그리고 그는 n개의 요리에 대한 만족도에 대한 데이터를 수집했습니다. 요리사는 1 단위 시간에 모든 요리를 요리할 수 있습니다. 요리의 유사 시간 계수는 실제로 걸리는 시간입니다.

이전 요리를 포함하여 해당 요리에 만족도를 Sotime[i]*satisfaction[i]를 곱하여 요리합니다.

요리사가 요리를 준비한 후 얻을 수 있는 Like-time 계수의 최대 합을 찾아야 합니다. 요리는 어떤 순서로든 준비할 수 있으며 요리사는 이 최대 가치를 얻기 위해 일부 요리를 버릴 수 있습니다.

따라서 입력이 [-1,-7,0,6,-7]과 같으면 출력은 17이 됩니다. 두 번째와 마지막 접시를 제거한 후 최대 총 유사 시간 계수는 -1*1 + 0*2 + 6*3 =17.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

505 x 505 크기의 배열 dp를 정의합니다.
solve() 함수를 정의하면 idx, time, array v,
가 필요합니다.
idx가 v의 크기와 같으면 -
- 0 반환
dp[idx, time]가 -1과 같지 않으면 -
- 반환 dp[idx, 시간]
ret :=-inf
ret :=solve(idx + 1, time, v) 및 v[idx] * time + solve(idx + 1, time + 1, v)의 최대값
dp[idx, time] :=ret
리턴 렛
주요 방법에서 다음을 수행하십시오 -
이 -1을 dp로 채우십시오.
배열 v
정렬
해결 반환(0, 1, v)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int dp[505][505];
   int solve(int idx, int time, vector <int>& v){
      if(idx == v.size()) return 0;
      if(dp[idx][time] != -1) return dp[idx][time];
      int ret = INT_MIN;
      ret = max(solve(idx + 1, time, v), v[idx] * time + solve(idx
      + 1, time + 1, v));
      return dp[idx][time] = ret;
   }
   int maxSatisfaction(vector<int>& v) {
      memset(dp, -1, sizeof(dp));
      sort(v.begin(), v.end());
      return solve(0, 1, v);
   }
};
main(){
   Solution ob;
   vector<int> v = {-1,-7,0,6,-7};
   cout << (ob.maxSatisfaction(v));
}

입력

{-1,-7,0,6,-7}