#**HƯỚNG DẪN:**<br>
Để tính được thiệt hại nhỏ nhất thì ra cần tính lượng triệt tiêu thiệt hại được nhiều nhất là bao nhiêu.<br>
**Ý tưởng ban đầu:**<br>
- Gọi dp[i] là lượng thiệt hại lớn nhất triệt tiêu được khi chọn các quả dưa chuột có thời hạn thu hoạch $<=i.$<br>
- Khi đó tính $dp[i],$ ta có công thức: Thêm một quả dưa chuột có thời hạn $i$ vào dãy quả của $dp[i-1]$ và loại bỏ quả có thiệt hại triệt tiêu được ít nhất nếu số lượng quả lúc đó $>i$(đến thời điểm $i$ chỉ có tối đa $i$ quả được thu hoạch mà có thời hạn nhỏ hơn $i.$ Ví dụ: $1,2,5,5,5$ với điều kiện bản thân dãy $1,2$ là $1$ dãy thỏa mãn.
- Kết quả là $dp[1000].$<br>
**Cải tiến:**<br>
- Chỉ cần xét các mốc $dp[i]$ mà $i$ có trong $n$ thời hạn thu hoạch được cho và kết quả cuối cùng chỉ cần quan tâm đến $dp[A].$(với $A$ là thời hạn thu hoạch lớn nhất trong $n$ quả) nên không cần tạo mảng $dp$ để lưu.<br>
- Ta nhập dữ liệu $ai,bi$ thành $inp[i].first,second$ và sort mảng theo phần tử $first.$ để xét từng mốc từ bé tới lớn.<br>
###**ĐÁP ÁN:** $sumall - sum$ (với $sumall$ là tổng thiệt hại cần xử lý và $sum$ là lượng thiệt hại lớn nhất xử lý được.<br>
##**CODE MẪU:**
```cpp
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,ans=0,sl=0,sumall=0;
pair<int,int> inp[1003];
priority_queue<int,vector<int>,greater<int>> pq;
bool cmp(pair<int,int>a,pair<int,int>b)
{
return a.first<b.first;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>inp[i].first;
for(int i=0;i<n;i++) cin>>inp[i].second,sumall+=inp[i].second;
sort(inp,inp+n,cmp);
for(int i=0;i<n;i++)
{
pq.push(inp[i].second);
ans+=inp[i].second;
sl++;
if(sl>inp[i].first) ans-=pq.top(),pq.pop(),sl--;
}
cout<<sumall-ans;
}
```
sharinganvanhoadong
Created at
3 likes