[E](E - Manhattan Multifocal Ellipse ())
Ideas for solving the problem
This problem seeks to satisfy\(\sum^n_{i=1}(|x-x_i|+|y-y_i|)\leq D\) coordinates of\((x,y)\) number of，Since it is a summation，the reason why\(x,y\) They are independent of each other.
- In the first step, let's first separately find the number of cells that satisfy\(\sum^n_{i=1}|x-x_i|\leq D\) cap (a poem)\(\sum^n_{i=1}|y-y_i|\leq D\) (used form a nominal expression)\(sum_x\)cap (a poem)\(sum_y\)The two are equivalent.
- In the second step, the results obtained in the first step are sorted and enumerated\(sum_x\)and then use dichotomies or double pointers to find a satisfying\(sum_y\)The answer is the cumulative total of the number of
For the first step, the array\(x\)Perform the sorting, noting that\(x\)The range is only\([-10^6,10^6]\)，\(D \leq 10^6\)So we can start with the\(min\_x-10^6\)Enumeration to\(max\_x+10^6\)enumerate the number of people who meet the\(sum_x\leq D\)(used form a nominal expression)\(sum_x\)I'm going to start by asking you again.\(sum_x\)The latter enumeration is done on the\(sum_x\)Dynamic maintenance is sufficient
coding
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
using piii = pair<int, pii>;
using pll=pair<ll,ll>;
using plll=pair<ll,pii>;
#define fi first
#define se second
const int INF = 0x3f3f3f3f;
void solve() {
int n,d;
cin>>n>>d;
vector<int> a(n),b(n);
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
}
auto get=[&](vector<int>&a){
vector<int> res;
sort((),());
if(()-()>d) return res;//A useless pruning.
int st=()-d;
ll sum=0;
for(int i=0;i<n;i++) sum+=abs(a[i]-st);
bool tag=false;
int cnt=0;
for(int i=st;i<=()+d;i++){
if(sum<=d) res.push_back(sum);
if(sum<=d) tag=true;//A useless pruning.
if(tag&&sum>d) break;//A useless pruning.
while(cnt<n&&i==a[cnt]) cnt++;
sum+=cnt-(n-cnt);
}
sort((),());
return res;
};
vector<int> xs=get(a),ys=get(b);
ll ans=0;
for(int i=0,j=()-1;i<();i++){//dual-pointer
while(j>=0&&ys[j]+xs[i]>d) j--;
ans+=j+1;
}
cout<<ans<<endl;
}
int main() {
(nullptr);
ios::sync_with_stdio(false);
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
return 0;
}
[F](F - Maximum Composition ())
Ideas for solving the problem
We start by fixing the chosen combination, which is necessarily chosen to have a length of\(K\)The next step is to consider the order of the combinations
insofar as\(A_i,B_i,A_{i+1},B_{i+1}\)Assuming that the first\(i\)In the front, the result is\(A_{i+1}*(A_i*x+B_i)+B_{i+1}\)that is\(A_iA_{i+1}*x+A_{i+1}B_i+B_{i+1}\)Assuming that the first\(i+1\)In the front, the result is\(A_iA_{i+1}*x+A_iB_{i+1}+B_i\), if the order of the former is due to the order of the latter, then the former equation is greater than the latter, which reduces to\((A_{i+1}-1)*B_i>(A_i-1)*B_{i+1}\)If you prioritize the pairs of numbers in such a way that it is optimal to choose them from the front to the back, then you can choose the pairs of numbers in such a way that it is optimal to choose
With the order determined, consider picking those pairs of numbers, and we define\(dp[i][j]\)before\(i\)I've got the right number.\(j\)The maximum value when the number of pairs of numbers and optimized to one dimension with a rolling array (similar to 01 backpack), the transfer equation is shown in the code
coding
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
using piii = pair<int, pii>;
using pll=pair<ll,ll>;
using plll=pair<ll,pii>;
#define fi first
#define se second
const int INF = 0x3f3f3f3f;
void solve() {
int n,k;
cin>>n>>k;
vector<pii> tup(n);
for(int i=0;i<n;i++){
auto &[a,b]=tup[i];
cin>>a>>b;
}
sort((),(),[&](pii A,pii B){
return (-1)*<(-1)*;
});
vector<ll> dp(k+1);
dp[0]=1;
for(int i=0;i<n;i++){
for(int j=k-1;j>=0;j--){
if(dp[j])
dp[j+1]=max(dp[j+1],dp[j]*tup[i].fi+tup[i].se);
}
}
cout<<dp[k]<<endl;
}
int main() {
(nullptr);
ios::sync_with_stdio(false);
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
return 0;
}