题目链接
题目思路
设\(dp[i][j][k]\)表示从 (1, 1) 走到 (i, j)，一路上收集了 k 个钻石时，钻石的单价最高能涨到多少，
由于数据随机所以每个节点不会有很多 我也不知道为啥
dp的时候贪心然后使用归并排序的思路合并
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=1e2+5,inf=0x3f3f3f3f,mod=51123987;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-7;
int n;
int a[maxn][maxn],b[maxn][maxn];
vector<pii> dp[maxn][maxn];
void add(pii x,vector<pii> &ans){
while(!ans.empty()&&ans.back().se<=x.se) ans.pop_back();
if(ans.empty()||ans.back().fi<x.fi) ans.push_back(x);
}
void mer(vector<pii> &a,vector<pii> &b,vector<pii> &ans){
int sa=a.size(),sb=b.size();
int i=0,j=0;
while(i<sa&&j<sb){
if(a[i].fi<b[j].fi){
add(a[i++],ans);
}else{
add(b[j++],ans);
}
}
while(i<sa){
add(a[i++],ans);
}
while(j<sb){
add(b[j++],ans);
}
}
int main(){
int _;scanf("%d",&_);
while(_--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
while(!dp[i][j].empty()) dp[i][j].pop_back();
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&b[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==1&&j==1){
dp[i][j].push_back({0,0});
}else if(i==1){
dp[i][j]=dp[i][j-1];
}else if(j==1){
dp[i][j]=dp[i-1][j];
}else{
mer(dp[i-1][j],dp[i][j-1],dp[i][j]);
}
for(int k=0;k<dp[i][j].size();k++){
dp[i][j][k].fi+=a[i][j];
dp[i][j][k].se+=b[i][j];
}
}
}
ll ans=0;
for(int k=0;k<dp[n][n].size();k++){
ans=max(ans,1ll*dp[n][n][k].fi*dp[n][n][k].se);
}
printf("%lld\n",ans);
}
return 0;
}