Rise in Price 题解(dp+随机数据)

题目链接

题目思路

设\(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;
}