2021杭电多校第3场 1009.Rise in Price

题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=6981

分析

对于每一个点，我们存下能到达它的点的所有的状态，并且这样一直推下去，每次给自己的状态排个序，a * b 大的排前面，只取前若干个（这里取100个），答案很大概率在这其中。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<P> V;
#define pb push_back
#define MP make_pair
#define fi first
#define se secondint n;
ll a[105][105],b[105][105];
vector<P> p[105][105];void solve(const V &x, const V &y, V &z)
{
    int sx = x.size();int sy = y.size();int i = 0, j = 0;while((i < sx || j < sy) && z.size() < 100){
    if(i < sx && j < sy) z.pb(x[i].fi * x[i].se > y[j].fi * y[j].se ? x[i++] : y[j++]);else if(i < sx) z.pb(x[i++]);else if(j < sy) z.pb(y[j++]);}
}bool cmp(P x, P y)
{
    return x.fi * x.se > y.fi * y.se;
}int main()
{
    int T = 1;scanf("%d",&T);while(T--){
    scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&a[i][j]), p[i][j].clear();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&b[i][j]);p[1][1].pb(MP(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) p[i][j].pb(p[i][j - 1][0]);else if(j == 1) p[i][j].pb(p[i - 1][j][0]);else solve(p[i - 1][j], p[i][j - 1], p[i][j]);for(int k=0;k<p[i][j].size();k++) p[i][j][k].fi += a[i][j], p[i][j][k].se += b[i][j];sort(p[i][j].begin(), p[i][j].end(), cmp);}ll ans = 0;for(int i=0;i<p[n][n].size();i++){
    ans = max(ans, p[n][n][i].fi * p[n][n][i].se);}printf("%lld\n",ans);}return 0;
}