[数据结构与算法]2021-07-27

HDU多校 Rise in Price

链接
题目链接
题意
两个100*100的矩阵,每次可以向下或者向右移动一格。每次移动可以在A矩阵的对应位置取得对应数量的宝石，同时宝石的价值会增长B矩阵对应的数值。问最后总的最大价值。
题解
用vector<pair<int,int>> f[N][N];存每一点的信息，其中pair的两个元素分别存已获得宝石的数量和宝石的价值，vector存在i，j这一位置有多少可能的情况，最后在终点遍历每一种情况求最值即可。
需要注意的是纯搜索复杂度过高，会TLE，可适当剪枝：因为按顺序遍历时宝石的数量是单增的，所以当一个点的宝石价值小于当前点的宝石价值时，该点的宝石数量一定小于当前的的宝石数量，所以这个点需要删除，不用传递给当前点。
代码

const int N=105;
vector<pair<int,int>> f[N][N];
int n,m;
int a[N][N],b[N][N];
ll ans;
pair<int,int> tmp[1000005];
//扩展节点
void ext(const pair<int,int>& p){
    while(m && tmp[m].second<=p.second)
        m--;
    if(!m || tmp[m].first<p.first)
        tmp[++m]=p;
}
//合并操作
void Union(const vector<pair<int,int>>&A,const vector<pair<int,int>>&B,vector<pair<int,int>>&C){
    int sa=A.size(),sb=B.size(),i=0,j=0;
    m=0;
    while(i<sa && j<sb){
        if(A[i].first<B[j].first)
            ext(A[i++]);
        else
            ext(B[j++]);
    }
    while(i<sa)
        ext(A[i++]);
    while(j<sb)
        ext(B[j++]);
    C.resize(m);
    for(i=0;i<m;++i)
        C[i]=tmp[i+1];
}
int  main(){

    int t;scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                scanf("%d",&a[i][j]);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                scanf("%d",&b[i][j]);
        f[1][1].resize(1);
        f[1][1][0]=make_pair(a[1][1],b[1][1]);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(i==1 && j==1)
                    continue;
                if(i==1)
                    f[i][j]=f[i][j-1];
                else if(j==1)
                    f[i][j]=f[i-1][j];
                else
                    Union(f[i-1][j],f[i][j-1],f[i][j]);
                for(int k=0;k<f[i][j].size();++k){
                    f[i][j][k].first+=a[i][j];
                    f[i][j][k].second+=b[i][j];
                    //printf("%d\n",f[i][j][k].first*f[i][j][k].second);
                }
                //printf("%d %d\n",i,j);
            }
        }
        ans=0;
        for(int i=0;i<f[n][n].size();++i)
            ans=max(ans,1ll*f[n][n][i].first*f[n][n][i].second);
        printf("%lld\n",ans);
    }
    return 0;
}